Fast FIND implementation (Quick FIND)
In this method, we use an array for the representation of the elements and their set names. As there can be many elements, we take the set names as integers itself. Example let us assume an array A[n] where A[i] denotes the set name where I belong to. This method will take O (1) time for accessing the array elements.
But using this as the FIND function, the UNION function will take O(n^{2}) time. For two elements a,b we first FIND(a) and FIND(b) i.e. their parents. Now if their parents are different then we have to change either set aâ€™s elements to point to bâ€™s parents or vice versa hence for every different parent we get we have to change all the elements in their sets which will take O(n) time and hence the overall complexity will become O(n^{2}).
So whatâ€™s the solution to this problem?
We optimise the UNION function at the cost of FIND.
Fast UNION implementation (Slow FIND)
The idea is to use a parent array along with the root/parent of a set which points to itself. Let us define the functions we have discussed earlier:

MAKESET(X): Creates a new set containing the single element X and, in the array, update the parent of X as X(root)

UNION (X, Y): Replaces the two sets containing X and Y by a single set which contains both of them

FIND(X): returns the name of the set that contains X. We keep on searching the Xâ€™s set until we find the root of that set
Initially we will create n set containing n single elements whose parents are themselves.
Here Union operation is just change the parent of one set to point to the root of another set hence the complexity is O(1). The FIND operation has the complexity as the depth of X in the tree.
Fast UNION implementation (Quick FIND)
In the previous method, we are getting to FIND complexity as O(n) in the worst case in a skew tree. So we need to optimise that method. For this, we use two ways:
 UNION by size(Union by weight) making the smaller tree a subtree of a larger tree.
 UNION by height(Union by rank) make the tree with less height a subtree of the tree with more height.
UNION by size refers to the same procedure as previous only this time we will mark every elementâ€™s parents as 1 initially, 1 will mean they are their own parent initially. We will increment the size of the parent once after the UNION of two sets. Letâ€™s take an example:
Initial Arrangement:
Now let suppose 1 and 2 are to be UNION then parent[1] = 2, parent[2] = 1, so the root element will contain the size of the set too.
Again for input of UNION 2 and 3:
Hence, we can see that we are directly getting the root along with their size i.e. the parent of a set and its size.
UNION by height (UNION by rank)
We store negative of height of the tree (that means, if the height of the tree is 2 then we store 2 in parent array). The height of a tree with 1 element is 1.
UNION by height implementation
For FIND operation no change in implementation.
UNION FIND using Path Compression
FIND operation traverses a list of nodes on the way to the root. We can make later FIND operations efficient by making each of these vertices point directly to root. This is called path compression. Lets see an example of this form.
Before FIND (X)
After FIND (X)
With path compression the only change to the function id that parent[X] is made equal to the value returned by FIND. That means after the root of the set is found recursively, X is made to point directly to it. This happen recursively to every node on the path to root.
FIND with path compression implementation
Path compression is compatible with UNION by size but not with UNION by height as there is no efficient way to change the height of the tree.
Now let us look at a easy to use version of UNION & FIND operation:
int FIND(int a){
if(a == parent[a])
return a;
return FIND(parent[a]);
}
Void UNION(int a,int b){
If(FIND(a) == parent(b))
Return;
Parent[a] = b;
}
Applications of UNION FIND algorithm
â€˘ Cycle Detection
â€˘ Job Sequencing
â€˘ Kruskalâ€™s Minimum Spanning Tree Algorithm
â€˘ In game theory algorithms
â€˘ Graph Algorithms
The above code is a simpler version of UNION finds to help understand the basic concept. Hope this is helpful to any aspiring.
You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.