Open In App

Introduction to Disjoint Set (Union-Find Algorithm)

Last Updated : 19 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

What is a Disjoint set data structure?

Two sets are called disjoint sets if they don’t have any element in common, the intersection of sets is a null set.

A data structure that stores non overlapping or disjoint subset of elements is called disjoint set data structure. The disjoint set data structure supports following operations:

  • Adding new sets to the disjoint set.
  • Merging disjoint sets to a single disjoint set using Union operation.
  • Finding representative of a disjoint set using Find operation.
  • Check if two sets are disjoint or not. 

Consider a situation with a number of persons and the following tasks to be performed on them:

  • Add a new friendship relation, i.e. a person x becomes the friend of another person y i.e adding new element to a set.
  • Find whether individual x is a friend of individual y (direct or indirect friend)

Examples: 

We are given 10 individuals say, a, b, c, d, e, f, g, h, i, j

Following are relationships to be added:
a <-> b  
b <-> d
c <-> f
c <-> i
j <-> e
g <-> j

Given queries like whether a is a friend of d or not. We basically need to create following 4 groups and maintain a quickly accessible connection among group items:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e, g, j}
G4 = {h}

Find whether x and y belong to the same group or not, i.e. to find if x and y are direct/indirect friends.

Partitioning the individuals into different sets according to the groups in which they fall. This method is known as a Disjoint set Union which maintains a collection of Disjoint sets and each set is represented by one of its members.

To answer the above question two key points to be considered are:

  • How to Resolve sets? Initially, all elements belong to different sets. After working on the given relations, we select a member as a representative. There can be many ways to select a representative, a simple one is to select with the biggest index.
  • Check if 2 persons are in the same group? If representatives of two individuals are the same, then they’ll become friends.

Data Structures used are: 

Array: An array of integers is called Parent[]. If we are dealing with N items, i’th element of the array represents the i’th item. More precisely, the i’th element of the Parent[] array is the parent of the i’th item. These relationships create one or more virtual trees.

Tree: It is a Disjoint set. If two elements are in the same tree, then they are in the same Disjoint set. The root node (or the topmost node) of each tree is called the representative of the set. There is always a single unique representative of each set. A simple rule to identify a representative is if ‘i’ is the representative of a set, then Parent[i] = i. If i is not the representative of his set, then it can be found by traveling up the tree until we find the representative.

Operations on Disjoint Set Data Structures:

  1. Find
  2. Union

1. Find:

Can be implemented by recursively traversing the parent array until we hit a node that is the parent of itself.

C++




// Finds the representative of the set
// that i is an element of
  
#include<bits/stdc++.h>
using namespace std;
  
int find(int i)
  
{
  
    // If i is the parent of itself
    if (parent[i] == i) {
  
        // Then i is the representative of
        // this set
        return i;
    }
    else {
  
        // Else if i is not the parent of
        // itself, then i is not the
        // representative of his set. So we
        // recursively call Find on its parent
        return find(parent[i]);
    }
}
  
// The code is contributed by Nidhi goel


Java




// Finds the representative of the set
// that i is an element of
import java.io.*;
  
class GFG {
  
    static int find(int i)
  
    {
  
        // If i is the parent of itself
        if (parent[i] == i) {
  
            // Then i is the representative of
            // this set
            return i;
        }
        else {
  
            // Else if i is not the parent of
            // itself, then i is not the
            // representative of his set. So we
            // recursively call Find on its parent
            return find(parent[i]);
        }
    }
}
  
// The code is contributed by Nidhi goel


Python3




# Finds the representative of the set
# that i is an element of
  
def find(i):
  
    # If i is the parent of itself
    if (parent[i] == i):
  
        # Then i is the representative of
        # this set
        return i
    else:
  
        # Else if i is not the parent of
        # itself, then i is not the
        # representative of his set. So we
        # recursively call Find on its parent
        return find(parent[i])
  
 # The code is contributed by Nidhi goel


C#




using System;
  
public class GFG{
  
    // Finds the representative of the set
    // that i is an element of
    public static int find(int i)
    {
  
        // If i is the parent of itself
        if (parent[i] == i) {
  
            // Then i is the representative of
            // this set
            return i;
        }
        else {
  
            // Else if i is not the parent of
            // itself, then i is not the
            // representative of his set. So we
            // recursively call Find on its parent
            return find(parent[i]);
        }
    }
}


Javascript




<script> 
// Finds the representative of the set
// that i is an element of
  
function find(i)
{
  
    // If i is the parent of itself
    if (parent[i] == i) {
  
        // Then i is the representative of
        // this set
        return i;
    }
    else {
  
        // Else if i is not the parent of
        // itself, then i is not the
        // representative of his set. So we
        // recursively call Find on its parent
        return find(parent[i]);
    }
}
// The code is contributed by Nidhi goel 
</script>


Time complexity: This approach is inefficient and can take O(n) time in worst case.

2. Union: 

It takes two elements as input and finds the representatives of their sets using the Find operation, and finally puts either one of the trees (representing the set) under the root node of the other tree.

C++




// Unites the set that includes i
// and the set that includes j
  
#include <bits/stdc++.h>
using namespace std;
  
void union(int i, int j) {
  
    // Find the representatives
    // (or the root nodes) for the set
    // that includes i
    int irep = this.Find(i),
  
    // And do the same for the set
    // that includes j
    int jrep = this.Find(j);
  
    // Make the parent of i’s representative
    // be j’s  representative effectively
    // moving all of i’s set into j’s set)
    this.Parent[irep] = jrep;
}


Java




import java.util.Arrays;
  
public class UnionFind {
    private int[] parent;
  
    public UnionFind(int size) {
        // Initialize the parent array with each element as its own representative
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
  
    // Find the representative (root) of the set that includes element i
    public int find(int i) {
        if (parent[i] == i) {
            return i; // i is the representative of its own set
        }
        // Recursively find the representative of the parent until reaching the root
        parent[i] = find(parent[i]); // Path compression
        return parent[i];
    }
  
    // Unite (merge) the set that includes element i and the set that includes element j
    public void union(int i, int j) {
        int irep = find(i); // Find the representative of set containing i
        int jrep = find(j); // Find the representative of set containing j
  
        // Make the representative of i's set be the representative of j's set
        parent[irep] = jrep;
    }
  
    public static void main(String[] args) {
        int size = 5; // Replace with your desired size
        UnionFind uf = new UnionFind(size);
  
        // Perform union operations as needed
        uf.union(1, 2);
        uf.union(3, 4);
  
        // Check if elements are in the same set
        boolean inSameSet = uf.find(1) == uf.find(2);
        System.out.println("Are 1 and 2 in the same set? " + inSameSet);
    }
}


Python3




# Unites the set that includes i
# and the set that includes j
  
def union(parent, rank, i, j):
    # Find the representatives
    # (or the root nodes) for the set
    # that includes i
    irep = find(parent, i)
      
    # And do the same for the set
    # that includes j
    jrep = find(parent, j)
      
    # Make the parent of i’s representative
    # be j’s  representative effectively
    # moving all of i’s set into j’s set)
      
    parent[irep] = jrep


C#




using System;
  
public class UnionFind
{
    private int[] parent;
  
    public UnionFind(int size)
    {
        // Initialize the parent array with each element as its own representative
        parent = new int[size];
        for (int i = 0; i < size; i++)
        {
            parent[i] = i;
        }
    }
  
    // Find the representative (root) of the set that includes element i
    public int Find(int i)
    {
        if (parent[i] == i)
        {
            return i; // i is the representative of its own set
        }
        // Recursively find the representative of the parent until reaching the root
        parent[i] = Find(parent[i]); // Path compression
        return parent[i];
    }
  
    // Unite (merge) the set that includes element i and the set that includes element j
    public void Union(int i, int j)
    {
        int irep = Find(i); // Find the representative of set containing i
        int jrep = Find(j); // Find the representative of set containing j
  
        // Make the representative of i's set be the representative of j's set
        parent[irep] = jrep;
    }
  
    public static void Main()
    {
        int size = 5; // Replace with your desired size
        UnionFind uf = new UnionFind(size);
  
        // Perform union operations as needed
        uf.Union(1, 2);
        uf.Union(3, 4);
  
        // Check if elements are in the same set
        bool inSameSet = uf.Find(1) == uf.Find(2);
        Console.WriteLine("Are 1 and 2 in the same set? " + inSameSet);
    }
}


Javascript




// JavaScript code for the approach
  
// Unites the set that includes i
// and the set that includes j
function union(parent, rank, i, j) 
{
  
// Find the representatives
// (or the root nodes) for the set
// that includes i
let irep = find(parent, i);
  
// And do the same for the set
// that includes j
let jrep = find(parent, j);
  
// Make the parent of i’s representative
// be j’s representative effectively
// moving all of i’s set into j’s set)
  
parent[irep] = jrep;
}


Time complexity: This approach is inefficient and could lead to tree of length O(n) in worst case.

Optimizations (Union by Rank/Size and Path Compression):

The efficiency depends heavily on which tree get attached to the other. There are 2 ways in which it can be done. First is Union by Rank, which considers height of the tree as the factor and Second is Union by Size, which considers size of the tree as the factor while attaching one tree to the other . This method along with Path Compression gives complexity of nearly constant time.

Path Compression (Modifications to Find()):

It speeds up the data structure by compressing the height of the trees. It can be achieved by inserting a small caching mechanism into the Find operation. Take a look at the code for more details:

C++




// Finds the representative of the set that i
// is an element of.
  
#include <bits/stdc++.h>
using namespace std;
  
int find(int i) 
{
  
    // If i is the parent of itself
    if (Parent[i] == i) {
  
        // Then i is the representative 
        return i;
    }
    else
  
        // Recursively find the representative.
        int result = find(Parent[i]);
  
        // We cache the result by moving i’s node 
        // directly under the representative of this
        // set
        Parent[i] = result;
        
        // And then we return the result
        return result;
     }
}


Java




// Finds the representative of the set that i
// is an element of.
import java.io.*;
import java.util.*;
  
static int find(int i) 
{
  
    // If i is the parent of itself
    if (Parent[i] == i) {
  
        // Then i is the representative 
        return i;
    }
    else
  
        // Recursively find the representative.
        int result = find(Parent[i]);
  
        // We cache the result by moving i’s node 
        // directly under the representative of this
        // set
        Parent[i] = result;
        
        // And then we return the result
        return result;
     }
}
  
// The code  is contributed by Arushi jindal.


Python3




#  Finds the representative of the set that i
# is an element of.
  
  
def find(i):
  
    # If i is the parent of itself
    if Parent[i] == i:
  
        # Then i is the representative 
        return i
    else:
  
        # Recursively find the representative.
        result = find(Parent[i])
  
        # We cache the result by moving i’s node 
        # directly under the representative of this
        # set
        Parent[i] = result
        
        # And then we return the result
        return result
  
# The code is contributed by Arushi  Jindal. 


C#




using System;
  
// Finds the representative of the set that i
// is an element of.
public static int find(int i) 
{
  
    // If i is the parent of itself
    if (Parent[i] == i) {
  
        // Then i is the representative 
        return i;
    }
    else
  
        // Recursively find the representative.
        int result = find(Parent[i]);
  
        // We cache the result by moving i’s node 
        // directly under the representative of this
        // set
        Parent[i] = result;
        
        // And then we return the result
        return result;
     }
}
  
// The code is contributed by Arushi Jindal.


Javascript




// Finds the representative of the set that i
// is an element of.
  
  
function find(i) 
{
  
    // If i is the parent of itself
    if (Parent[i] == i) {
  
        // Then i is the representative 
        return i;
    }
    else
  
        // Recursively find the representative.
        let result = find(Parent[i]);
  
        // We cache the result by moving i’s node 
        // directly under the representative of this
        // set
        Parent[i] = result;
        
        // And then we return the result
        return result;
     }
}
  
// The code is contributed by Arushi  Jindal.


Time Complexity: O(log n) on average per call.

Union by Rank:

First of all, we need a new array of integers called rank[]. The size of this array is the same as the parent array Parent[]. If i is a representative of a set, rank[i] is the height of the tree representing the set. 
Now recall that in the Union operation, it doesn’t matter which of the two trees is moved under the other. Now what we want to do is minimize the height of the resulting tree. If we are uniting two trees (or sets), let’s call them left and right, then it all depends on the rank of left and the rank of right

  • If the rank of left is less than the rank of right, then it’s best to move left under right, because that won’t change the rank of right (while moving right under left would increase the height). In the same way, if the rank of right is less than the rank of left, then we should move right under left.
  • If the ranks are equal, it doesn’t matter which tree goes under the other, but the rank of the result will always be one greater than the rank of the trees.
     

C++




// Unites the set that includes i and the set
// that includes j by rank
  
#include <bits/stdc++.h>
using namespace std;
  
void unionbyrank(int i, int j) {
  
    // Find the representatives (or the root nodes)
    // for the set that includes i
    int irep = this.find(i);
  
    // And do the same for the set that includes j
    int jrep = this.Find(j);
  
    // Elements are in same set, no need to
    // unite anything.
    if (irep == jrep)
        return;
      
      // Get the rank of i’s tree
    irank = Rank[irep],
  
    // Get the rank of j’s tree
    jrank = Rank[jrep];
  
    // If i’s rank is less than j’s rank
    if (irank < jrank) {
  
        // Then move i under j
        this.parent[irep] = jrep;
    }
  
    // Else if j’s rank is less than i’s rank
    else if (jrank < irank) {
  
        // Then move j under i
        this.Parent[jrep] = irep;
    }
  
    // Else if their ranks are the same
    else {
  
        // Then move i under j (doesn’t matter
        // which one goes where)
        this.Parent[irep] = jrep;
  
        // And increment the result tree’s
        // rank by 1
        Rank[jrep]++;
    }
}


Java




public class DisjointSet {
  
    private int[] parent;
    private int[] rank;
  
    // Constructor to initialize the DisjointSet data
    // structure
    public DisjointSet(int size)
    {
        parent = new int[size];
        rank = new int[size];
  
        // Initialize each element as a separate set with
        // rank 0
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
  
    // Function to find the representative (or the root
    // node) of a set with path compression
    private int find(int i)
    {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // Path compression
        }
        return parent[i];
    }
  
    // Unites the set that includes i and the set that
    // includes j by rank
    public void unionByRank(int i, int j)
    {
        // Find the representatives (or the root nodes) for
        // the set that includes i and j
        int irep = find(i);
        int jrep = find(j);
  
        // Elements are in the same set, no need to unite
        // anything
        if (irep == jrep) {
            return;
        }
  
        // Get the rank of i's tree
        int irank = rank[irep];
  
        // Get the rank of j's tree
        int jrank = rank[jrep];
  
        // If i's rank is less than j's rank
        if (irank < jrank) {
            // Move i under j
            parent[irep] = jrep;
        }
        // Else if j's rank is less than i's rank
        else if (jrank < irank) {
            // Move j under i
            parent[jrep] = irep;
        }
        // Else if their ranks are the same
        else {
            // Move i under j (doesn't matter which one goes
            // where)
            parent[irep] = jrep;
            // Increment the result tree's rank by 1
            rank[jrep]++;
        }
    }
  
    // Example usage
    public static void main(String[] args)
    {
        int size = 5;
        DisjointSet ds = new DisjointSet(size);
  
        // Perform some union operations
        ds.unionByRank(0, 1);
        ds.unionByRank(2, 3);
        ds.unionByRank(1, 3);
  
        // Find the representative of each element and print
        // the result
        for (int i = 0; i < size; i++) {
            System.out.println(
                "Element " + i
                + " belongs to the set with representative "
                + ds.find(i));
        }
    }
}


Python3




class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
  
    # Function to find the representative (or the root node) of a set
    def find(self, i):
        # If i is not the representative of its set, recursively find the representative
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]
  
    # Unites the set that includes i and the set that includes j by rank
    def union_by_rank(self, i, j):
        # Find the representatives (or the root nodes) for the set that includes i and j
        irep = self.find(i)
        jrep = self.find(j)
  
        # Elements are in the same set, no need to unite anything
        if irep == jrep:
            return
  
        # Get the rank of i's tree
        irank = self.rank[irep]
  
        # Get the rank of j's tree
        jrank = self.rank[jrep]
  
        # If i's rank is less than j's rank
        if irank < jrank:
            # Move i under j
            self.parent[irep] = jrep
        # Else if j's rank is less than i's rank
        elif jrank < irank:
            # Move j under i
            self.parent[jrep] = irep
        # Else if their ranks are the same
        else:
            # Move i under j (doesn't matter which one goes where)
            self.parent[irep] = jrep
            # Increment the result tree's rank by 1
            self.rank[jrep] += 1
  
    def main(self):
        # Example usage
        size = 5
        ds = DisjointSet(size)
  
        # Perform some union operations
        ds.union_by_rank(0, 1)
        ds.union_by_rank(2, 3)
        ds.union_by_rank(1, 3)
  
        # Find the representative of each element
        for i in range(size):
            print(f"Element {i} belongs to the set with representative {ds.find(i)}")
  
  
# Creating an instance and calling the main method
ds = DisjointSet(size=5)
ds.main()


C#




using System;
  
class DisjointSet {
    private int[] parent;
    private int[] rank;
  
    public DisjointSet(int size) {
        parent = new int[size];
        rank = new int[size];
  
        // Initialize each element as a separate set
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
  
    // Function to find the representative (or the root node) of a set
    private int Find(int i) {
        // If i is not the representative of its set, recursively find the representative
        if (parent[i] != i) {
            parent[i] = Find(parent[i]); // Path compression
        }
        return parent[i];
    }
  
    // Unites the set that includes i and the set that includes j by rank
    public void UnionByRank(int i, int j) {
        // Find the representatives (or the root nodes) for the set that includes i and j
        int irep = Find(i);
        int jrep = Find(j);
  
        // Elements are in the same set, no need to unite anything
        if (irep == jrep) {
            return;
        }
  
        // Get the rank of i's tree
        int irank = rank[irep];
  
        // Get the rank of j's tree
        int jrank = rank[jrep];
  
        // If i's rank is less than j's rank
        if (irank < jrank) {
            // Move i under j
            parent[irep] = jrep;
        }
        // Else if j's rank is less than i's rank
        else if (jrank < irank) {
            // Move j under i
            parent[jrep] = irep;
        }
        // Else if their ranks are the same
        else {
            // Move i under j (doesn't matter which one goes where)
            parent[irep] = jrep;
            // Increment the result tree's rank by 1
            rank[jrep]++;
        }
    }
  
    static void Main() {
        // Example usage
        int size = 5;
        DisjointSet ds = new DisjointSet(size);
  
        // Perform some union operations
        ds.UnionByRank(0, 1);
        ds.UnionByRank(2, 3);
        ds.UnionByRank(1, 3);
  
        // Find the representative of each element
        for (int i = 0; i < size; i++) {
            Console.WriteLine("Element " + i + " belongs to the set with representative " + ds.Find(i));
        }
    }
}


Javascript




// JavaScript Program for the above approach
unionbyrank(i, j) {
let irep = this.find(i); // Find representative of set including i
let jrep = this.find(j); // Find representative of set including j
  
if (irep === jrep) {
return; // Elements are already in the same set
}
  
let irank = this.rank[irep]; // Rank of set including i
let jrank = this.rank[jrep]; // Rank of set including j
  
if (irank < jrank) {
this.parent[irep] = jrep; // Make j's representative parent of i's representative
} else if (jrank < irank) {
this.parent[jrep] = irep; // Make i's representative parent of j's representative
} else {
this.parent[irep] = jrep; // Make j's representative parent of i's representative
this.rank[jrep]++;        // Increment the rank of the resulting set
}


Union by Size:

Again, we need a new array of integers called size[]. The size of this array is the same as the parent array Parent[]. If i is a representative of a set, size[i] is the number of the elements in the tree representing the set. 
Now we are uniting two trees (or sets), let’s call them left and right, then in this case it all depends on the size of left and the size of right tree (or set).

  • If the size of left is less than the size of right, then it’s best to move left under right and increase size of right by size of left. In the same way, if the size of right is less than the size of left, then we should move right under left. and increase size of left by size of right.
  • If the sizes are equal, it doesn’t matter which tree goes under the other.

C++




// Unites the set that includes i and the set
// that includes j by size
  
#include <bits/stdc++.h>
using namespace std;
  
void unionBySize(int i, int j) {
  
    // Find the representatives (or the root nodes)
    // for the set that includes i
    int irep = find(i);
  
    // And do the same for the set that includes j
    int jrep = find(j);
  
    // Elements are in the same set, no need to
    // unite anything.
    if (irep == jrep)
        return;
  
    // Get the size of i’s tree
    int isize = Size[irep];
  
    // Get the size of j’s tree
    int jsize = Size[jrep];
  
    // If i’s size is less than j’s size
    if (isize < jsize) {
  
        // Then move i under j
        Parent[irep] = jrep;
  
        // Increment j's size by i's size
        Size[jrep] += Size[irep];
    }
  
    // Else if j’s size is less than i’s size
    else {
  
        // Then move j under i
        Parent[jrep] = irep;
  
        // Increment i's size by j's size
        Size[irep] += Size[jrep];
    }
}


Java




// Java program for the above approach
import java.util.Arrays;
  
class UnionFind {
  
    private int[] Parent;
    private int[] Size;
  
    public UnionFind(int n)
    {
        // Initialize Parent array
        Parent = new int[n];
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
        }
  
        // Initialize Size array with 1s
        Size = new int[n];
        Arrays.fill(Size, 1);
    }
  
    // Function to find the representative (or the root
    // node) for the set that includes i
    public int find(int i)
    {
        if (Parent[i] != i) {
            // Path compression: Make the parent of i the
            // root of the set
            Parent[i] = find(Parent[i]);
        }
        return Parent[i];
    }
  
    // Unites the set that includes i and the set that
    // includes j by size
    public void unionBySize(int i, int j)
    {
        // Find the representatives (or the root nodes) for
        // the set that includes i
        int irep = find(i);
  
        // And do the same for the set that includes j
        int jrep = find(j);
  
        // Elements are in the same set, no need to unite
        // anything.
        if (irep == jrep)
            return;
  
        // Get the size of i’s tree
        int isize = Size[irep];
  
        // Get the size of j’s tree
        int jsize = Size[jrep];
  
        // If i’s size is less than j’s size
        if (isize < jsize) {
            // Then move i under j
            Parent[irep] = jrep;
  
            // Increment j's size by i's size
            Size[jrep] += Size[irep];
        }
        // Else if j’s size is less than i’s size
        else {
            // Then move j under i
            Parent[jrep] = irep;
  
            // Increment i's size by j's size
            Size[irep] += Size[jrep];
        }
    }
}
  
public class GFG {
  
    public static void main(String[] args)
    {
        // Example usage
        int n = 5;
        UnionFind unionFind = new UnionFind(n);
  
        // Perform union operations
        unionFind.unionBySize(0, 1);
        unionFind.unionBySize(2, 3);
        unionFind.unionBySize(0, 4);
  
        // Print the representative of each element after
        // unions
        for (int i = 0; i < n; i++) {
            System.out.println("Element " + i
                               + ": Representative = "
                               + unionFind.find(i));
        }
    }
}
  
// This code is contributed by Susobhan Akhuli


Python3




# Python program for the above approach
class UnionFind:
    def __init__(self, n):
        # Initialize Parent array
        self.Parent = list(range(n))
  
        # Initialize Size array with 1s
        self.Size = [1] * n
  
    # Function to find the representative (or the root node) for the set that includes i
    def find(self, i):
        if self.Parent[i] != i:
            # Path compression: Make the parent of i the root of the set
            self.Parent[i] = self.find(self.Parent[i])
        return self.Parent[i]
  
    # Unites the set that includes i and the set that includes j by size
    def unionBySize(self, i, j):
        # Find the representatives (or the root nodes) for the set that includes i
        irep = self.find(i)
  
        # And do the same for the set that includes j
        jrep = self.find(j)
  
        # Elements are in the same set, no need to unite anything.
        if irep == jrep:
            return
  
        # Get the size of i’s tree
        isize = self.Size[irep]
  
        # Get the size of j’s tree
        jsize = self.Size[jrep]
  
        # If i’s size is less than j’s size
        if isize < jsize:
            # Then move i under j
            self.Parent[irep] = jrep
  
            # Increment j's size by i's size
            self.Size[jrep] += self.Size[irep]
        # Else if j’s size is less than i’s size
        else:
            # Then move j under i
            self.Parent[jrep] = irep
  
            # Increment i's size by j's size
            self.Size[irep] += self.Size[jrep]
  
# Example usage
n = 5
unionFind = UnionFind(n)
  
# Perform union operations
unionFind.unionBySize(0, 1)
unionFind.unionBySize(2, 3)
unionFind.unionBySize(0, 4)
  
# Print the representative of each element after unions
for i in range(n):
    print("Element {}: Representative = {}".format(i, unionFind.find(i)))
  
# This code is contributed by Susobhan Akhuli


C#




using System;
  
class UnionFind
{
    private int[] Parent;
    private int[] Size;
  
    public UnionFind(int n)
    {
        // Initialize Parent array
        Parent = new int[n];
        for (int i = 0; i < n; i++)
        {
            Parent[i] = i;
        }
  
        // Initialize Size array with 1s
        Size = new int[n];
        for (int i = 0; i < n; i++)
        {
            Size[i] = 1;
        }
    }
  
    // Function to find the representative (or the root node) for the set that includes i
    public int Find(int i)
    {
        if (Parent[i] != i)
        {
            // Path compression: Make the parent of i the root of the set
            Parent[i] = Find(Parent[i]);
        }
        return Parent[i];
    }
  
    // Unites the set that includes i and the set that includes j by size
    public void UnionBySize(int i, int j)
    {
        // Find the representatives (or the root nodes) for the set that includes i
        int irep = Find(i);
  
        // And do the same for the set that includes j
        int jrep = Find(j);
  
        // Elements are in the same set, no need to unite anything.
        if (irep == jrep)
            return;
  
        // Get the size of i’s tree
        int isize = Size[irep];
  
        // Get the size of j’s tree
        int jsize = Size[jrep];
  
        // If i’s size is less than j’s size
        if (isize < jsize)
        {
            // Then move i under j
            Parent[irep] = jrep;
  
            // Increment j's size by i's size
            Size[jrep] += Size[irep];
        }
        // Else if j’s size is less than i’s size
        else
        {
            // Then move j under i
            Parent[jrep] = irep;
  
            // Increment i's size by j's size
            Size[irep] += Size[jrep];
        }
    }
}
  
class Program
{
    static void Main()
    {
        // Example usage
        int n = 5;
        UnionFind unionFind = new UnionFind(n);
  
        // Perform union operations
        unionFind.UnionBySize(0, 1);
        unionFind.UnionBySize(2, 3);
        unionFind.UnionBySize(0, 4);
  
        // Print the representative of each element after unions
        for (int i = 0; i < n; i++)
        {
            Console.WriteLine($"Element {i}: Representative = {unionFind.Find(i)}");
        }
    }
}


Javascript




unionbysize(i, j) {
        let irep = this.find(i); // Find the representative of the set containing i.
        let jrep = this.find(j); // Find the representative of the set containing j.
  
        if (irep === jrep) {
            return; // Elements are already in the same set.
        }
  
        let isize = this.size[irep]; // Size of the set including i.
        let jsize = this.size[jrep]; // Size of the set including j.
  
        if (isize < jsize) {
            // If i's size is less than j's size, make i's representative 
            // a child of j's representative.
            this.parent[irep] = jrep;
            this.size[jrep] += this.size[irep]; // Increment j's size by i's size.
        } else {
            // If j's size is less than or equal to i's size, make j's representative 
            // a child of i's representative.
            this.parent[jrep] = irep;
            this.size[irep] += this.size[jrep]; // Increment i's size by j's size.
            if (isize === jsize) {
                // If sizes are equal, increment the rank of i's representative.
                this.rank[irep]++;
            }
        }
    }


Output

Element 0: Representative = 0
Element 1: Representative = 0
Element 2: Representative = 2
Element 3: Representative = 2
Element 4: Representative = 0


Time complexity: O(log n) without Path Compression.

Below is the complete implementation of disjoint set with path compression and union by rank.

C++




// C++ implementation of disjoint set
  
#include <bits/stdc++.h>
using namespace std;
  
class DisjSet {
    int *rank, *parent, n;
  
public:
    
    // Constructor to create and
    // initialize sets of n items
    DisjSet(int n)
    {
        rank = new int[n];
        parent = new int[n];
        this->n = n;
        makeSet();
    }
  
    // Creates n single item sets
    void makeSet()
    {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
  
    // Finds set of given item x
    int find(int x)
    {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x) {
  
            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);
  
            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }
  
        return parent[x];
    }
  
    // Do union of two sets by rank represented
    // by x and y.
    void Union(int x, int y)
    {
        // Find current sets of x and y
        int xset = find(x);
        int yset = find(y);
  
        // If they are already in same set
        if (xset == yset)
            return;
  
        // Put smaller ranked item under
        // bigger ranked item if ranks are
        // different
        if (rank[xset] < rank[yset]) {
            parent[xset] = yset;
        }
        else if (rank[xset] > rank[yset]) {
            parent[yset] = xset;
        }
  
        // If ranks are same, then increment
        // rank.
        else {
            parent[yset] = xset;
            rank[xset] = rank[xset] + 1;
        }
    }
};
  
// Driver Code
int main()
{
    
      // Function Call
    DisjSet obj(5);
    obj.Union(0, 2);
    obj.Union(4, 2);
    obj.Union(3, 1);
    
    if (obj.find(4) == obj.find(0))
        cout << "Yes\n";
    else
        cout << "No\n";
    if (obj.find(1) == obj.find(0))
        cout << "Yes\n";
    else
        cout << "No\n";
  
    return 0;
}


Java




// A Java program to implement Disjoint Set Data
// Structure.
import java.io.*;
import java.util.*;
  
class DisjointUnionSets {
    int[] rank, parent;
    int n;
  
    // Constructor
    public DisjointUnionSets(int n)
    {
        rank = new int[n];
        parent = new int[n];
        this.n = n;
        makeSet();
    }
  
    // Creates n sets with single item in each
    void makeSet()
    {
        for (int i = 0; i < n; i++) {
            // Initially, all elements are in
            // their own set.
            parent[i] = i;
        }
    }
  
    // Returns representative of x's set
    int find(int x)
    {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x) {
            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);
  
            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }
  
        return parent[x];
    }
  
    // Unites the set that includes x and the set
    // that includes x
    void union(int x, int y)
    {
        // Find representatives of two sets
        int xRoot = find(x), yRoot = find(y);
  
        // Elements are in the same set, no need
        // to unite anything.
        if (xRoot == yRoot)
            return;
  
        // If x's rank is less than y's rank
        if (rank[xRoot] < rank[yRoot])
  
            // Then move x under y  so that depth
            // of tree remains less
            parent[xRoot] = yRoot;
  
        // Else if y's rank is less than x's rank
        else if (rank[yRoot] < rank[xRoot])
  
            // Then move y under x so that depth of
            // tree remains less
            parent[yRoot] = xRoot;
  
        else // if ranks are the same
        {
            // Then move y under x (doesn't matter
            // which one goes where)
            parent[yRoot] = xRoot;
  
            // And increment the result tree's
            // rank by 1
            rank[xRoot] = rank[xRoot] + 1;
        }
    }
}
  
// Driver code
public class Main {
    public static void main(String[] args)
    {
        // Let there be 5 persons with ids as
        // 0, 1, 2, 3 and 4
        int n = 5;
        DisjointUnionSets dus = 
                new DisjointUnionSets(n);
  
        // 0 is a friend of 2
        dus.union(0, 2);
  
        // 4 is a friend of 2
        dus.union(4, 2);
  
        // 3 is a friend of 1
        dus.union(3, 1);
  
        // Check if 4 is a friend of 0
        if (dus.find(4) == dus.find(0))
            System.out.println("Yes");
        else
            System.out.println("No");
  
        // Check if 1 is a friend of 0
        if (dus.find(1) == dus.find(0))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Python3




# Python3 program to implement Disjoint Set Data
# Structure.
  
class DisjSet:
    def __init__(self, n):
        # Constructor to create and
        # initialize sets of n items
        self.rank = [1] * n
        self.parent = [i for i in range(n)]
  
  
    # Finds set of given item x
    def find(self, x):
          
        # Finds the representative of the set
        # that x is an element of
        if (self.parent[x] != x):
              
            # if x is not the parent of itself
            # Then x is not the representative of
            # its set,
            self.parent[x] = self.find(self.parent[x])
              
            # so we recursively call Find on its parent
            # and move i's node directly under the
            # representative of this set
  
        return self.parent[x]
  
  
    # Do union of two sets represented
    # by x and y.
    def Union(self, x, y):
          
        # Find current sets of x and y
        xset = self.find(x)
        yset = self.find(y)
  
        # If they are already in same set
        if xset == yset:
            return
  
        # Put smaller ranked item under
        # bigger ranked item if ranks are
        # different
        if self.rank[xset] < self.rank[yset]:
            self.parent[xset] = yset
  
        elif self.rank[xset] > self.rank[yset]:
            self.parent[yset] = xset
  
        # If ranks are same, then move y under
        # x (doesn't matter which one goes where)
        # and increment rank of x's tree
        else:
            self.parent[yset] = xset
            self.rank[xset] = self.rank[xset] + 1
  
# Driver code
obj = DisjSet(5)
obj.Union(0, 2)
obj.Union(4, 2)
obj.Union(3, 1)
if obj.find(4) == obj.find(0):
    print('Yes')
else:
    print('No')
if obj.find(1) == obj.find(0):
    print('Yes')
else:
    print('No')
  
# This code is contributed by ng24_7.


C#




// A C# program to implement  
// Disjoint Set Data Structure.
using System;
      
class DisjointUnionSets 
{
    int[] rank, parent;
    int n;
  
    // Constructor
    public DisjointUnionSets(int n)
    {
        rank = new int[n];
        parent = new int[n];
        this.n = n;
        makeSet();
    }
  
    // Creates n sets with single item in each
    public void makeSet()
    {
        for (int i = 0; i < n; i++)
        {
            // Initially, all elements are in
            // their own set.
            parent[i] = i;
        }
    }
  
    // Returns representative of x's set
    public int find(int x)
    {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x)
        {
              
            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);
  
            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }
        return parent[x];
    }
  
    // Unites the set that includes x and
    // the set that includes x
    public void union(int x, int y)
    {
        // Find representatives of two sets
        int xRoot = find(x), yRoot = find(y);
  
        // Elements are in the same set, 
        // no need to unite anything.
        if (xRoot == yRoot)
            return;
  
        // If x's rank is less than y's rank
        if (rank[xRoot] < rank[yRoot])
  
            // Then move x under y so that depth
            // of tree remains less
            parent[xRoot] = yRoot;
  
        // Else if y's rank is less than x's rank
        else if (rank[yRoot] < rank[xRoot])
  
            // Then move y under x so that depth of
            // tree remains less
            parent[yRoot] = xRoot;
  
        else // if ranks are the same
        {
            // Then move y under x (doesn't matter
            // which one goes where)
            parent[yRoot] = xRoot;
  
            // And increment the result tree's
            // rank by 1
            rank[xRoot] = rank[xRoot] + 1;
        }
    }
}
  
// Driver code
class GFG 
{
    public static void Main(String[] args)
    {
        // Let there be 5 persons with ids as
        // 0, 1, 2, 3 and 4
        int n = 5;
        DisjointUnionSets dus = 
                new DisjointUnionSets(n);
  
        // 0 is a friend of 2
        dus.union(0, 2);
  
        // 4 is a friend of 2
        dus.union(4, 2);
  
        // 3 is a friend of 1
        dus.union(3, 1);
  
        // Check if 4 is a friend of 0
        if (dus.find(4) == dus.find(0))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
  
        // Check if 1 is a friend of 0
        if (dus.find(1) == dus.find(0))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
  
// This code is contributed by Rajput-Ji


Javascript




class DisjSet {
    constructor(n) {
        this.rank = new Array(n);
        this.parent = new Array(n);
        this.n = n;
        this.makeSet();
    }
  
    makeSet() {
        for (let i = 0; i < this.n; i++) {
            this.parent[i] = i;
        }
    }
  
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
  
    Union(x, y) {
        let xset = this.find(x);
        let yset = this.find(y);
  
        if (xset === yset) return;
  
        if (this.rank[xset] < this.rank[yset]) {
            this.parent[xset] = yset;
        } else if (this.rank[xset] > this.rank[yset]) {
            this.parent[yset] = xset;
        } else {
            this.parent[yset] = xset;
            this.rank[xset] = this.rank[xset] + 1;
        }
    }
}
  
// usage example
let obj = new DisjSet(5);
obj.Union(0, 2);
obj.Union(4, 2);
obj.Union(3, 1);
  
if (obj.find(4) === obj.find(0)) {
  console.log("Yes");
} else {
  console.log("No");
}
if (obj.find(1) === obj.find(0)) {
  console.log("Yes");
} else {
  console.log("No");
}


Output

Yes
No



Time complexity: O(n) for creating n single item sets . The two techniques -path compression with the union by rank/size, the time complexity will reach nearly constant time. It turns out, that the final amortized time complexity is O(α(n)), where α(n) is the inverse Ackermann function, which grows very steadily (it does not even exceed for n<10600  approximately).

Space complexity: O(n) because we need to store n elements in the Disjoint Set Data Structure.



Next Article

Similar Reads

Disjoint Set Union (Randomized Algorithm)
A Disjoint set union is an algorithm that is used to manage a collection of disjoint sets. A disjoint set is a set in which the elements are not in any other set. Also, known as union-find or merge-find. The disjoint set union algorithm allows you to perform the following operations efficiently: Find: Determine which set a given element belongs to.
15+ min read
Union-Find Algorithm | (Union By Rank and Find by Optimized Path Compression)
Check whether a given graph contains a cycle or not. Example: Input: Output: Graph contains Cycle. Input: Output: Graph does not contain Cycle. Prerequisites: Disjoint Set (Or Union-Find), Union By Rank and Path CompressionWe have already discussed union-find to detect cycle. Here we discuss find by path compression, where it is slightly modified t
13 min read
Disjoint Set Union on trees | Set 2
Given a tree, and the cost of a subtree is defined as |S|*AND(S) where |S| is the size of the subtree and AND(S) is bitwise AND of all indices of nodes from the subtree, task is to find maximum cost of possible subtree. Prerequisite : Disjoint Set Union Examples: Input : Number of nodes = 4 Edges = (1, 2), (3, 4), (1, 3) Output : Maximum cost = 4 E
14 min read
Union By Rank and Path Compression in Union-Find Algorithm
In the previous post, we introduced union find algorithm and used it to detect cycles in a graph. We used the following union() and find() operations for subsets. C/C++ Code // Naive implementation of find int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // Naive implementation of union() void Union(i
15+ min read
Disjoint Set Union on Trees
Given a tree and weights of nodes. Weights are non-negative integers. Task is to find maximum size of a subtree of a given tree such that all nodes are even in weights. Prerequisite : Disjoint Set Union Examples : Input : Number of nodes = 7 Weights of nodes = 1 2 6 4 2 0 3 Edges = (1, 2), (1, 3), (2, 4), (2, 5), (4, 6), (6, 7) Output : Maximum siz
11 min read
Extended Disjoint Set Union on Trees
Prerequisites: DFS, Trees, DSUGiven a tree with of N nodes from value 1 to N and E edges and array arr[] which denotes number associated to each node. You are also given Q queries which contains 2 integers {V, F}. For each query, there is a subtree with vertex V, the task is to check if there exists count of numbers associated with each node in tha
15 min read
Test case generator for Tree using Disjoint-Set Union
In this article, we will generate test cases such that given set edges form a Tree. Below are the two conditions of the Tree: It should have one less edge than the number of vertices.There should be no cycle in it. Approach: The idea is to run a loop and add one edge each time that is generated randomly, and for adding each edge we will check wheth
11 min read
Number of connected components of a graph ( using Disjoint Set Union )
Given an undirected graph G with vertices numbered in the range [0, N] and an array Edges[][] consisting of M edges, the task is to find the total number of connected components in the graph using Disjoint Set Union algorithm. Examples: Input: N = 4, Edges[][] = {{1, 0}, {2, 3}, {3, 4}}Output: 2Explanation: There are only 2 connected components as
7 min read
Calculate number of nodes between two vertices in an acyclic Graph by Disjoint Union method
Given a connected acyclic graph, a source vertex and a destination vertex, your task is to count the number of vertices between the given source and destination vertex by Disjoint Union Method . Examples: Input : 1 4 4 5 4 2 2 6 6 3 1 3 Output : 3 In the input 6 is the total number of vertices labeled from 1 to 6 and the next 5 lines are the connec
10 min read
Find the number of Islands using Disjoint Set
Given a boolean 2D matrix, find the number of islands.A group of connected 1s forms an island. For example, the below matrix contains 5 islands {1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1} A cell in the 2D matrix can be connected to 8 neighbours. This is a variation of the standard problem: “Counting the numbe
15+ min read
three90RightbarBannerImg