A disjoint-set data structure (also called union-find data structure) is a data structure that tracks a set of elements partitioned into a number of disjoint (overlapping) subsets.
Operations
Union: Add new sets/merge existing sets
Find: Determine whether elements are in the same set
Algorithm
The representative element (one without a parent, or whose parent is itself) is used to represent a subset
All the elements in a subset compose a tree structure whose root is representative element
if an element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element is reached at the root of the tree
If the representative element of the two elements is the same, then they belong to the same subset
Code Snippets
Initialization
Use a struct or class
1 2 3 4 5 6 7
#define MAX 10000 structNode { int data; int rank; int parent; }node[MAX]
Use arrays of the same size
1 2 3 4 5 6 7 8
intset[max]; // the representative element of a subset where the certain element in int rank[max]; int data[max];
voidmakeSet(int i){ set[I]=i; rank[i]=0; }
Find Function
struct or class
1 2 3 4 5 6 7 8
// find the representative element of a subset recursively intfind(int x){ // if a node's parent is itself, then it is the representative element if(node[x].parent==x) return x; // else recursively find its parent return find(node[x].parent) }
array
1 2 3 4 5 6 7
intfind(int i){ // if a node's parent is itself, then it is the representative element if(set[i]==i) returnset[i]; // else recursively find its parent return find(set[i]) }
Union
struct or class
1 2 3 4 5 6 7 8 9 10 11
voidunion(int a, int b){ a=find(a); b=find(b); if(node[a].rank>node[b].rank) node[b].parent=a; else{ node[a].parent=b; if(node[a].rank==node[b].rank) node[b].rank++; } }
array
1 2 3 4 5 6 7 8 9 10 11
voidunion(int I, int j) { I=find(I); j=find(j); if(i==j) return ; if(rank[i]>rank[j]) set[j]=i; else{ if(rank[i]==rank[j]) rank[j]++; set[i]=j; } }
Related Problems
Compute the number of disjoint subsets -> count the number of nodes whose parent is itself, i.e. parent[i]==i