Disjoint Set | Union-Find Algorithm – Union by rank and path compression

Earlier we have seen the complete implementation of Disjoint Set. We strongly recommend reading this before continue.

Disjoint Set operations –

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

Click here to read about these operations in detail.

How Disjoint Set is optimized:

  • Union by rank.
  • Path by compression.

Union by rank:

Uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as O(n). We can optimize it by using union by rank.

Union by rank always attaches the shorter tree to the root of the taller tree.

To implement union by rank, each element is associated with a rank. Initially a set has one element and a rank of zero.

If we union two sets and

  • Both trees have the same rank – the resulting set’s rank is one larger
  • Both trees have the different ranks – the resulting set’s rank is the larger of the two. Ranks are used instead of height or depth because path compression will change the trees’ heights over time.

Worst case complexity: O(LogN)


disjoint set - Union by Rank

Pseudo Code:

function Union(x, y)
   xRoot := Find(x)
   yRoot := Find(y)
   // x and y are already in the same set
   if xRoot == yRoot            
   // x and y are not in same set, so we merge them
    if xRoot.rank < yRoot.rank 
      xRoot.parent := yRoot 
    else if xRoot.rank > yRoot.rank
      yRoot.parent := xRoot
     xRoot.parent := yRoot
     yRoot.rank   := yRoot.rank + 1

Path compression:

Path compression` is a way of flattening the structure of the tree whenever Find is used on it. Since each element visited on the way to a root is part of the same set, all of these visited elements can be reattached directly to the root. The resulting tree is much flatter, speeding up future operations not only on these elements, but also on those referencing them.


disjoint set - Path Compression

Pseudo code:

function Find(x)
   if x.parent != x
     x.parent := Find(x.parent)
   return x.parent


The MakeSet operation makes a new set by creating a new element with a unique id, a rank of 0, and a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set.

The MakeSet operation has O(1) time complexity.

Pseudo code:

 function MakeSet(x)
   if x is not already present:
     add x to the disjoint-set tree
     x.parent := x
     x.rank   := 0


import java.util.*;
public class OptimizedDisjointSet {
static class Edge{
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
static class SubSet {
int parent;
int rank;
static class Graph{
int vertices;
LinkedList<Edge>[] adjList;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices){
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i <vertices ; i++) {
adjList[i] = new LinkedList<>();
public void addEgde(int source, int destination){
Edge edge = new Edge(source, destination);
allEdges.add(edge); //add to total edges
//(Path Compression)
public int find(SubSet [] subSet, int vertex){
subSet[vertex].parent = find(subSet, subSet[vertex].parent);;
return subSet[vertex].parent;
//(Union by rank)
public void union(SubSet [] subSet, int x, int y){
int x_set_parent = find(subSet, x);
int y_set_parent = find(subSet, y);
//attach the smaller rank tree to the higher rank tree
//make x as parent of y
subSet[y_set_parent].parent = x_set_parent;
}else if(subSet[x_set_parent].rank<subSet[y_set_parent].rank){
//make y as parent of x
subSet[x_set_parent].parent = y_set_parent;
// make any tree child of other tree
subSet[y_set_parent].parent = x_set_parent;
//now increase the rank of x for the next time
public void makeSet(SubSet[] subSets) {
//make set
for (int i = 0; i < vertices; i++) {
subSets[i] = new SubSet();
subSets[i].parent = i;
subSets[i].rank = 0;
public void disjointSets(){
//create a subsets []
SubSet[] subSets = new SubSet[vertices];
// //makeset
//iterate through all the edges and keep making the sets
for (int i = 0; i <allEdges.size() ; i++) {
Edge edge = allEdges.get(i);
int x_set = find(subSets, edge.source);
int y_set = find(subSets, edge.destination);
//check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if(x_set==y_set) {
//do nothing
union(subSets, x_set, y_set);
public void printSets(SubSet[] subSets){
//Find different Sets
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i <subSets.length ; i++) {
ArrayList<Integer> list = map.get(subSets[i].parent);
list.add(i);//add vertex
ArrayList<Integer> list = new ArrayList<>();
//Print the Different sets
Set<Integer> set = map.keySet();
Iterator<Integer> iterator = set.iterator();
int key = iterator.next();
System.out.println("Set Id: " + key + " elements: " + map.get(key));
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1);
graph.addEgde(0, 2);
graph.addEgde(1, 3);
graph.addEgde(4, 5);
System.out.println("Disjoint Sets: ");


Disjoint Sets:
Set Id: 0 elements: [0, 1, 2, 3]
Set Id: 4 elements: [4, 5]

Ref: wiki