Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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 }

◆ 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 }
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:
CreateSet
void CreateSet(int n)
Definition: disjoint_set.cpp:37
std::vector
STL class.
Find
int Find(int x)
Definition: disjoint_set.cpp:53
std::cout
endl
#define endl
Definition: matrix_exponentiation.cpp:36
InSameUnion
bool InSameUnion(int x, int y)
Definition: disjoint_set.cpp:67
Union
void Union(int x, int y)
Definition: disjoint_set.cpp:78