Category: Disjoint Set

Path Compression and Union by Rank are two optimization techniques used in Disjoint Set Data Structure. These techniques help to improve the efficiency of the Disjoint Set operations like Find, Union, and MakeSet.

Path Compression

As the name suggests, Path Compression is a technique that compresses the path from a node to the root of the tree. When we perform a Find operation on a node, we traverse the path from the node to the root of the tree. During this traversal, we update the parent of each node to the root of the tree.

It helps to reduce the height of the tree and improves the efficiency of the Find operation.

Algorithm for Path Compression

Here is the algorithm for Path Compression −

1. If the node is the root of the tree, return the node
2. Otherwise, recursively find the root of the tree
3. Update the parent of the node to the root of the tree
4. Return the root of the tree

Code for Path Compression

Let’s see the code for Path Compression in C, C++, Java, and Python −

CC++JavaPython

// C program to implement Path Compression in Disjoint Set#include <stdio.h>#define N 100int parent[N];int rank[N];voidmakeSet(int n){for(int i =0; i < n; i++){
      parent[i]= i;}}intfind(int x){if(parent[x]!= x){
      parent[x]=find(parent[x]);}return parent[x];}voidunionSet(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){
         parent[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){
         parent[rootX]= rootY;}else{
         parent[rootY]= rootX;
         rank[rootX]++;}}}intmain(){int n =5;makeSet(n);unionSet(0,1);unionSet(1,2);unionSet(3,4);printf("Find(2): %d\n",find(2));printf("Find(3): %d\n",find(3));return0;}

Output

Following is the output of the above C code −

Find(2): 0
Find(3): 3

Union by Rank

Union by Rank is another optimization technique used in Disjoint Set Data Structure. In this technique, we maintain the rank of each node in the tree. The rank of a node is the height of the tree rooted at that node. When we perform a Union operation, we merge the tree with a smaller rank into the tree with a larger rank.

It helps to keep the height of the tree as small as possible and improves the efficiency of the Union operation.

Algorithm for Union by Rank

Here is the algorithm for Union by Rank −

1. Find the root of the tree for the given nodes.
2. If the rank of the root of the first tree is greater than the rank of the root of the second tree, make the root of the second tree as the child of the root of the first tree.
3. Otherwise, make the root of the first tree as the child of the root of the second tree.
4. If the rank of the root of the first tree is equal to the rank of the root of the second tree, increment the rank of the root of the second tree by 1.

Code for Union by Rank

Let’s see the code for Union by Rank in C, C++, Java, and Python −

CC++JavaPython

// C program to implement Union by Rank in Disjoint Set#include <stdio.h>#define N 100int parent[N];int rank[N];voidmakeSet(int n){for(int i =0; i < n; i++){
      parent[i]= i;
      rank[i]=0;}}intfind(int x){if(parent[x]!= x){
      parent[x]=find(parent[x]);}return parent[x];}voidunionSet(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){
         parent[rootY]= rootX;}else{
         parent[rootX]= rootY;if(rank[rootX]== rank[rootY]){
            rank[rootY]++;}}}}intmain(){int n =5;makeSet(n);unionSet(0,1);unionSet(1,2);unionSet(3,4);printf("Find(2): %d\n",find(2));printf("Find(3): %d\n",find(3));return0;}

Output

Following is the output of the above C code −

Find(2): 0
Find(3): 3

Comparison of Path Compression and Union by Rank

Let’s compare the efficiency of the Disjoint Set operations with and without Path Compression and Union by Rank −

Operation	Without Optimization	With Path Compression	With Union by Rank	With Path Compression and Union by Rank
MakeSet	O(1)	O(1)	O(1)	O(1)
Find	O(n)	O(log n)	O(log n)
Union	O(n)	O(log n)	O(log n)	O(log n)

Conclusion

Path Compression and Union by Rank are two optimization techniques used in Disjoint Set Data Structure. These techniques help to improve the efficiency of the Disjoint Set operations like Find, Union, and MakeSet.

Using both Path Compression and Union by Rank, we can keep the height of the tree as small as possible and improve the efficiency of the Disjoint Set operations.

Disjoint set also known as union-find data structure. It is a type of data structure that keeps track of a collection of elements that are partitioned into multiple non-overlapping (one element can be in only one set) disjoint sets.

It provides operations for adding (merging) two sets, finding the representative of the set to which an element belongs, and finding if two elements are in the same set.

Imagine you have a group of students. Initially, each student is in his/her own group. Over time, some students form their own groups due to common interests, and these groups can merge with other groups.

For example,

Initially :  {A}, {B}, {C}, {D}, {E} (Each student is in his/her own group)
Then A and B form a group : {A, B}, {C}, {D}, {E}
Then C and D form a group : {A, B}, {C, D}, {E}
Then A, B, C, D form a group : {A, B, C, D}, {E}

In the above example, we can see that the students are partitioned into multiple disjoint sets. They also merge with other sets to form a bigger set. Here, we can use disjoint set data structure to keep track of these sets.

Key Features of Disjoint Set

Following are the key features of disjoint set data structure:

• Non-overlapping sets: Each element can belong to only one set.
• Dynamic merging: We can merge two sets into one using Union operation.
• Efficient querying: With the find operation, we can quickly find which set an element belongs to.

Operations on Disjoint Set

Following are the operations that can be performed on disjoint set:

• Find(x): Find the representative of the set to which element x belongs.
• Union(x, y): Merge the sets to which elements x and y belong.
• MakeSet(x): Create a new set with element x.

Implementation of Disjoint Set

Disjoint set can be implemented using the following data structures:

• Array: We can use an array to store the parent of each element. The parent of an element is the representative of the set to which the element belongs.
• Rank: We can use rank to optimize the union operation. Rank is the height of the tree rooted at an element. We always attach the smaller tree to the larger tree to keep the height of the tree small.

Example code for Disjoint Set using Array

Following is the example code for disjoint set using array:

In order to implement disjoint set using array, we need to create a structure that contains an array to store the parent of each element and the number of elements in the set. We will also cover the following operations −

• MakeSet(x)
• Find(x)
• Union(x, y)

These operations will help us to create a new set with element x, find the representative of the set to which element x belongs and merge the sets to which elements x and y belong.

Algorithm

We need to follow the following steps to implement disjoint set using array:

1. Create a new set with element x using MakeSet(x) operation.
2. Find the representative of the set to which element x belongs using Find(x) operation.
3. Merge the sets to which elements x and y belong using Union(x, y) operation.

Code

Following is code for implementing disjoint set using array:

CC++JavaPython

#include <stdio.h>#include <stdlib.h>// Disjoint set data structurestructDisjointSet{int*parent;int n;};// Create a new set with element xvoidMakeSet(structDisjointSet*ds,int x){
   ds->parent[x]= x;}// Find the representative of the set to which element x belongsintFind(structDisjointSet*ds,int x){if(ds->parent[x]== x)return x;returnFind(ds, ds->parent[x]);}// Merge the sets to which elements x and y belongvoidUnion(structDisjointSet*ds,int x,int y){int xset =Find(ds, x);int yset =Find(ds, y);
   ds->parent[xset]= yset;}intmain(){structDisjointSet ds;int n =5;
   ds.n = n;
   ds.parent =(int*)malloc(n *sizeof(int));for(int i =0; i < n; i++)MakeSet(&ds, i);Union(&ds,0,1);Union(&ds,2,3);Union(&ds,0,2);for(int i =0; i < n; i++)printf("%d ", ds.parent[i]);return0;}

Output

Following is the output of the above code:

1 3 3 3 4

Complexity of Disjoint Set Operations

Following are the time complexities of disjoint set operations:

• Find(x): O(log n) where n is the number of elements.
• Union(x, y): O(log n) where n is the number of elements.
• MakeSet(x): O(1)

Applications of Disjoint Set

Following are the applications of disjoint set data structure:

• Connected Components: Disjoint set can be used to find connected components in a graph.
• Dynamic connectivity: It is also used to find if two elements are connected in a graph.
• Image processing: It is used to find connected components in an image.
• Kruskal’s algorithm: We can use disjoint set to find minimum spanning tree using Kruskal’s algorithm.
• Network connectivity: You can check if two computers are connected in a network.