Disjoint Set Union / Union Find Algorithm Simplified

Union Find algorithm is a crucial algorithm in problems related to graph data structure. It helps find the relation between vertices by using the existing edges and tells whether the two are related or not.

It is very useful in real-world scenarios like for example, LinkedIn uses this algorithm to display the users information about the degree of connection with other users. People who are direct parent to the user are the 1st level connection, people who are the parent of the parent of the user are the 2nd level connection and so on.

You might be thinking what is this parent thing I mentioned so much about? It's just a directed edge between the two nodes, in our case, an edge from user to another person makes and edge like user -> another person. In real life it translates to user "follows/is a friend of" another person.

Union Find algorithm includes two methods:

1. Find - to get the root representative of the set in which the current vertex belongs to. (uses Path Compression for optimization)
2. Union - Tells whether the two vertices are in the same set or not, and if not merges them into a single set. (uses Rank to decide the resultant merged set)

Here, are some basic things we should know before diving in:

• Each vertex initially belongs to its own set, and therefore is the root representative of that set. It is implemented as an array generally.
• Each vertex initially is assigned the same rank which others have, here we assign 0. It is also implemented as an array generally.

Let's implement the find() method first as it is required in the union() method later.

int find(int i, int[] parent)

We take a vertex i and the parent array to find the root representative of the vertex i and return it.

int root = parent[i];

We get the parent of the i from the array. Initially we would get the element itself, if there are no relations (merging) yet.

// parent of the vertex is not the root representative
if (root != parent[root])
    return parent[i] = find(root, parent);

// parent of the vertex is the root representative
return root;

First, we check if the parent of the vertex is the root of the set to which the vertex belongs to? if yes then we simply return it, as it was the main goal of our function.

But, if not, then we recursively try to find the root until the parent and vertex are same and assign it in the parent array.

Think of it like this, if the vertex and the parent of vertex are the same, then it is the root representative of the set in which it belongs. Once we find it we return it.

For a more clearer visual representation of the find() function refer this image

Here, as you can see the path from 7 to the root (ie. 1) was from 7 -> 3 -> 1 and after calling find(7) which in turn calls find(3) and later assigns the parent of 7 as 1. It can be clearly seen from the image that the path is reduced, keeping all the vertices still in the same set. Just we get the compressed path of the root of the vertex from this function.

Now, comes the union() method. After understanding find(), it is just a piece of cake.

boolean union(int i, int j, int[] parent, int[] rank) 

We take the two vertices to unite into a single set, the parent array and the rank array.

int iRoot = find(i, parent);
int jRoot = find(j, parent);

// both vertices belong to the same set already
if (iRoot == jRoot)
    return false;

Firstly, we just get the roots of both the vertices using the previously defined find() method.

If the roots returned by both the method calls are same, then it would simply mean that they are already in the same set and we can't unite it further. That's why we return false.

if (rank[iRoot] > rank[jRoot])
    parent[jRoot] = iRoot;

else if (rank[iRoot] < parent[jRoot])
    parent[iRoot] = jRoot;

Now, just compare the ranks of both vertices and merge the smaller ranking vertex to the set of the greater ranking vertex. Now you might think, if we don't modify the rank here, then how they can be compared in the first place? We modify the rank when the ranks of both vertices are found to be same.

else {
    parent[iRoot] = jRoot;
    rank[jRoot]++;
}

We can merge any vertex into the other vertex's set, but we have to make sure that we increase the rank of the set in which the vertex have been merged or rather "united" by 1.

return true;

At the end of the if-else ladder, if we reach there, we return true. It indicates that the vertices have been "united" to a single set and the "union" operation was successful!

You can implement this in any language as the syntax used here is generic and can be applied to implement in most of the languages with little to no change.

I have implemented it in java and here is the full code for reference.

public class DSU {
    // finds the root of a given vertex's set with path compression
    private static int find(int i, int[] parent) {
        // the root is not the vertex itself
        int root = parent[i];

        // the root of this vertex isn't the root of the set
        if (root != parent[root])
            // update the current vertex's parent with the root of its 
            // current parent's root to compress path
            return parent[i] = DSU.find(root, parent);

        // the root of this vertex is also the root of the set
        return root;
    }

    // checks the root of both the vertices and assign new roots 
    private static boolean union(int i, int j, int[] parent, int[] rank) {
        int iRoot = DSU.find(i, parent);
        int jRoot = DSU.find(j, parent);

        if (iRoot == jRoot)
            return false;

        if (rank[iRoot] > rank[jRoot])
            parent[jRoot] = iRoot;

        else if (rank[iRoot] < parent[jRoot])
            parent[iRoot] = jRoot;

        else {
            parent[iRoot] = jRoot;
            rank[jRoot]++;
        }

        return true;
    }
}

Thank you for reading! Follow me and stay tuned in for more such simplified explanations.