Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
disjoint_set.cpp File Reference

Disjoint Sets Data Structure (Disjoint Sets) More...

#include <iostream>
#include <vector>
Include dependency graph for disjoint_set.cpp:

Functions

void CreateSet (int n)
 
int Find (int x)
 
bool InSameUnion (int x, int y)
 
void Union (int x, int y)
 
int main ()
 

Variables

vector< int > root
 
vector< int > rank
 

Detailed Description

Disjoint Sets Data Structure (Disjoint Sets)

Author
leoyang429

A disjoint set data structure (also called union find or merge find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. Some situations where disjoint sets can be used are- to find connected components of a graph, kruskal's algorithm for finding Minimum Spanning Tree etc. There are two operation which we perform on disjoint sets - 1) Union 2) Find

Function Documentation

◆ CreateSet()

void CreateSet ( int n)

Function to create a set

Parameters
nnumber of element
37 {
38 root = vector<int>(n + 1);
39 rank = vector<int>(n + 1, 1);
40 for (int i = 1; i <= n; ++i) {
41 root[i] = i;
42 }
43}

◆ Find()

int Find ( int x)

Find operation takes a number x and returns the set to which this number belongs to.

Parameters
xelement of some set
Returns
set to which x belongs to
53 {
54 if (root[x] == x) {
55 return x;
56 }
57 return root[x] = Find(root[x]);
58}
int Find(int x)
Definition disjoint_set.cpp:53
Here is the call graph for this function:

◆ InSameUnion()

bool InSameUnion ( int x,
int y )

A utility function to check if x and y are from same set or not

Parameters
xelement of some set
yelement of some set
67{ return Find(x) == Find(y); }
Here is the call graph for this function:

◆ main()

int main ( void )

Main function

93 {
94 // tests CreateSet & Find
95 int n = 100;
96 CreateSet(n);
97 for (int i = 1; i <= 100; ++i) {
98 if (root[i] != i) {
99 cout << "Fail" << endl;
100 break;
101 }
102 }
103 // tests InSameUnion & Union
104 cout << "1 and 2 are initially not in the same subset" << endl;
105 if (InSameUnion(1, 2)) {
106 cout << "Fail" << endl;
107 }
108 Union(1, 2);
109 cout << "1 and 2 are now in the same subset" << endl;
110 if (!InSameUnion(1, 2)) {
111 cout << "Fail" << endl;
112 }
113 return 0;
114}
void CreateSet(int n)
Definition disjoint_set.cpp:37
bool InSameUnion(int x, int y)
Definition disjoint_set.cpp:67
void Union(int x, int y)
Definition disjoint_set.cpp:78
#define endl
Definition matrix_exponentiation.cpp:36
Here is the call graph for this function:

◆ Union()

void Union ( int x,
int y )

Union operation combines two disjoint sets to make a single set in this union function we pass two elements and check if they are from different sets then combine those sets

Parameters
xelement of some set
yelement of some set
78 {
79 int a = Find(x), b = Find(y);
80 if (a != b) {
81 if (rank[a] < rank[b]) {
82 root[a] = b;
83 } else if (rank[a] > rank[b]) {
84 root[b] = a;
85 } else {
86 root[a] = b;
87 ++rank[b];
88 }
89 }
90}
Here is the call graph for this function: