In this article, we will cover one of the very interesting problems when it comes to competitive algorithms - Disjoint Set Union.
The Problem
Sources said that on a planet named Earth, people formed different communities based on their living principles. Each one had a different terminology, different festivals, different clothing styles and different ways of worshipping the Supreme/God.
Kapi wanted to keep track of which human was part of which community. Owing to the huge population of Earth, ministers were now in trouble as to how to accomplish this humongous task.
Formal Introduction of the Problem
We need to maintain a collection T = { T1 , T2 , …... , Tn } of disjoint dynamic sets. By disjoint we mean that each object belongs to exactly one set.
Each set can be identified by a representative, which is also a member of the set. Let x denote an object, we wish to support the following operations:
UNION(x, y): Unites two disjoint sets that contain x and y into a new set.
FIND(x, y): Checks whether two elements x and y are connected or not.
Starting with each set as an individual unit, we perform the UNION operation as per the relation between the objects. As we were asked to keep track of the connectivity of the sets, the FIND operation comes to the rescue .
Let's take an example:
Consider a set T = { 0, 1 , 2 , 3 , 4 , 5 }. Initially, all of them are disjoint.
We use an array of size equal to that of T, i.e., 6, the indices of whom represent the elements of the set, while the value stored at respective indices are the parent of that element.
As we have 6 subsets initially, (the value nodes are showing are the indices of their parent),
Initially everyone is their own parent (we are assuming disjoint subsets) , so array stores the index itself.
Our array v , which stores parent of the corresponding node , is :
Let us check out some operations:
1) Union(2, 5)
We are asked to combine node '2' and node '5' into one set. We first find the parent of both the nodes. Both are representative of themselves. We make '5' as the representative of node '2', by storing '5' as the parent of '2' in our array, and let '5' be happy with whatever it holds (as initially, we have assumed that all sets are all by themselves). This way, we have merged the two nodes into one, and now whenever FIND operation will be called, it will see that parent of '2' and '5' are just the same, so they both belong to the same subset, and will return the same.
Array contents:
Note that the content of other nodes remains just the same. The only change is at the value stored at index '2', which now stores it's new parent representative.
2) Union(1, 3)
We should join nodes '1' and '3'. We obtain the parent of both the nodes, which is the same for both nodes for this case as well. So we simply store '3' as the representative of node '1' and let node '3' keep storing its own index.
Array contents:
3) Union(1, 5)
First check the parent of the set containing node '1' and node '5'. The parent of node '1' is '3', while that of node '5' is '5' itself. In order to merge the two sets, make all the nodes of the set containing the node '1' store parent of '5' as their parent, which is also '5' in this case (confusing, not at all).
Let us simplify it. there are two nodes in the subset to which node '1' belongs. These are nodes '3' and '1'. So save '5' at these indices. That's pretty much all we have to do!
Array contents:
4) Find(2, 3)
Alright, new task.
Check out the parent of the two nodes. How? Lookup in the array. Both '2' and '3' store '5'. So, are they same? Yes, they are!
As these two belong to the same subset, return true.
5) Union(0, 4)
Ah, the union again. Check out the parents of the two. Both of them are still singleton set. Simply join them by storing '4' at the index '0'.
Array contents:
So finally we have two connected components.
6) Find(1, 4)
Do these two nodes belong to the same subset? Check the figure above.
As they belong to different subsets, return false.
Implementation of the Problem
Coding up Find is quite easy. We are only required to compare the indices of the two elements and if they are equal, then return true, otherwise returns false.
Each element of the subset stores the index of its parent, while the root element stores its own index.
To perform union operation, make the root of one set storing the root of another set so that all of the subset entities already become a subset of the other set.
So to get the root of a subset, simply go on the parent of v[id],
until v[id] == id, which signifies that we have reached root.
Here we have the code:
void init()
{
for(int i = 0; i < N; i++)
{
v[i] = i;
}
}
int root(int x)
{
while(v[x] != x)
{
x = v[x];
}
return x;
}
bool find(int x, int y)
{
if(root(x) == root(y))
return true;
else
return false;
}
void uni(int x, int y)
{
int i = root(x);
int j = root(y);
v[ i ] = j;
}
Time Complexity:
O(n)
Improving the Code
The above strategy performs union operation in linear time in the worst case. Like when merging, we can check who should be assigned root of whom.
So we will go for what is called weighted union operation. We assign a weight to the root node as per the number of elements the subset contains.
Here we have the code:
void init()
{
for(i = 0; i < N; i++)
{
v[i] =i;
size[i] = 1;
}
}
void weighted_uni(int x,int y)
{
int p = root(x);
int q = root(y);
if(size[p] > size[q])
{
root[q] = root[p];
size[p] += size[q];
}
else
{
root[p] = root[q];
size[q] += size[p];
}
}
Complexity:
O(log n)
Going Further with Improvement
Taking union with path compression. Instead of jumping to the parent element, go for the grandparent.
Here is the code:
int comp_root(int id)
{
while(v[id]!=id)
{
v[id] = v[v[id]];
id = v[id];
}
return id;
}
So with this, we have successfully coded the solution for the Disjoint Set Union problem. If you are confused and have queries related to any particular step of the solution, please do comment below and clear all your doubts. I will be more than happy to assist. Happy Coding!
