Disjoint Sets Data Structure (Disjoint Sets)
More...
#include <iostream>
#include <vector>
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
◆ CreateSet()
Function to create a set
- Parameters
-
37 {
40 for (int i = 1; i <= n; ++i) {
41 root[i] = i;
42 }
43}
◆ Find()
Find operation takes a number x and returns the set to which this number belongs to.
- Parameters
-
- 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
◆ InSameUnion()
bool InSameUnion |
( |
int | x, |
|
|
int | y ) |
A utility function to check if x and y are from same set or not
- Parameters
-
x | element of some set |
y | element of some set |
◆ main()
Main function
93 {
94
95 int n = 100;
97 for (int i = 1; i <= 100; ++i) {
98 if (root[i] != i) {
100 break;
101 }
102 }
103
104 cout <<
"1 and 2 are initially not in the same subset" <<
endl;
107 }
109 cout <<
"1 and 2 are now in the same subset" <<
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
◆ 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
-
x | element of some set |
y | element of some set |
78 {
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}