Introduction to Disjoint Set (Union-Find Algorithm)
Last Updated :
14 Feb, 2024
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:
- Find
- Union
1. Find:
Can be implemented by recursively traversing the parent array until we hit a node that is the parent of itself.
C++
#include<bits/stdc++.h>
using namespace std;
int find(int i)
{
if (parent[i] == i) {
return i;
}
else {
return find(parent[i]);
}
}
|
Java
import java.io.*;
class GFG {
static int find(int i)
{
if (parent[i] == i) {
return i;
}
else {
return find(parent[i]);
}
}
}
|
Python3
def find(i):
if (parent[i] == i):
return i
else:
return find(parent[i])
|
C#
using System;
public class GFG{
public static int find(int i)
{
if (parent[i] == i) {
return i;
}
else {
return find(parent[i]);
}
}
}
|
Javascript
<script>
function find(i)
{
if (parent[i] == i) {
return i;
}
else {
return find(parent[i]);
}
}
</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++
#include <bits/stdc++.h>
using namespace std;
void union(int i, int j) {
int irep = this.Find(i),
int jrep = this.Find(j);
this.Parent[irep] = jrep;
}
|
Java
import java.util.Arrays;
public class UnionFind {
private int[] parent;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int find(int i) {
if (parent[i] == i) {
return i;
}
parent[i] = find(parent[i]);
return parent[i];
}
public void union(int i, int j) {
int irep = find(i);
int jrep = find(j);
parent[irep] = jrep;
}
public static void main(String[] args) {
int size = 5;
UnionFind uf = new UnionFind(size);
uf.union(1, 2);
uf.union(3, 4);
boolean inSameSet = uf.find(1) == uf.find(2);
System.out.println("Are 1 and 2 in the same set? " + inSameSet);
}
}
|
Python3
def union(parent, rank, i, j):
irep = find(parent, i)
jrep = find(parent, j)
parent[irep] = jrep
|
C#
using System;
public class UnionFind
{
private int[] parent;
public UnionFind(int size)
{
parent = new int[size];
for (int i = 0; i < size; i++)
{
parent[i] = i;
}
}
public int Find(int i)
{
if (parent[i] == i)
{
return i;
}
parent[i] = Find(parent[i]);
return parent[i];
}
public void Union(int i, int j)
{
int irep = Find(i);
int jrep = Find(j);
parent[irep] = jrep;
}
public static void Main()
{
int size = 5;
UnionFind uf = new UnionFind(size);
uf.Union(1, 2);
uf.Union(3, 4);
bool inSameSet = uf.Find(1) == uf.Find(2);
Console.WriteLine("Are 1 and 2 in the same set? " + inSameSet);
}
}
|
Javascript
function union(parent, rank, i, j)
{
let irep = find(parent, i);
let jrep = find(parent, j);
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.
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++
#include <bits/stdc++.h>
using namespace std;
int find(int i)
{
if (Parent[i] == i) {
return i;
}
else {
int result = find(Parent[i]);
Parent[i] = result;
return result;
}
}
|
Java
import java.io.*;
import java.util.*;
static int find(int i)
{
if (Parent[i] == i) {
return i;
}
else {
int result = find(Parent[i]);
Parent[i] = result;
return result;
}
}
|
Python3
def find(i):
if Parent[i] == i:
return i
else:
result = find(Parent[i])
Parent[i] = result
return result
|
C#
using System;
public static int find(int i)
{
if (Parent[i] == i) {
return i;
}
else {
int result = find(Parent[i]);
Parent[i] = result;
return result;
}
}
|
Javascript
function find(i)
{
if (Parent[i] == i) {
return i;
}
else {
let result = find(Parent[i]);
Parent[i] = result;
return result;
}
}
|
Time Complexity: O(log n) on average per call.
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++
#include <bits/stdc++.h>
using namespace std;
void unionbyrank(int i, int j) {
int irep = this.find(i);
int jrep = this.Find(j);
if (irep == jrep)
return;
irank = Rank[irep],
jrank = Rank[jrep];
if (irank < jrank) {
this.parent[irep] = jrep;
}
else if (jrank < irank) {
this.Parent[jrep] = irep;
}
else {
this.Parent[irep] = jrep;
Rank[jrep]++;
}
}
|
Java
public class DisjointSet {
private int[] parent;
private int[] rank;
public DisjointSet(int size)
{
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
private int find(int i)
{
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
public void unionByRank(int i, int j)
{
int irep = find(i);
int jrep = find(j);
if (irep == jrep) {
return;
}
int irank = rank[irep];
int jrank = rank[jrep];
if (irank < jrank) {
parent[irep] = jrep;
}
else if (jrank < irank) {
parent[jrep] = irep;
}
else {
parent[irep] = jrep;
rank[jrep]++;
}
}
public static void main(String[] args)
{
int size = 5;
DisjointSet ds = new DisjointSet(size);
ds.unionByRank(0, 1);
ds.unionByRank(2, 3);
ds.unionByRank(1, 3);
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
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union_by_rank(self, i, j):
irep = self.find(i)
jrep = self.find(j)
if irep == jrep:
return
irank = self.rank[irep]
jrank = self.rank[jrep]
if irank < jrank:
self.parent[irep] = jrep
elif jrank < irank:
self.parent[jrep] = irep
else:
self.parent[irep] = jrep
self.rank[jrep] += 1
def main(self):
size = 5
ds = DisjointSet(size)
ds.union_by_rank(0, 1)
ds.union_by_rank(2, 3)
ds.union_by_rank(1, 3)
for i in range(size):
print(f"Element {i} belongs to the set with representative {ds.find(i)}")
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];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
private int Find(int i) {
if (parent[i] != i) {
parent[i] = Find(parent[i]);
}
return parent[i];
}
public void UnionByRank(int i, int j) {
int irep = Find(i);
int jrep = Find(j);
if (irep == jrep) {
return;
}
int irank = rank[irep];
int jrank = rank[jrep];
if (irank < jrank) {
parent[irep] = jrep;
}
else if (jrank < irank) {
parent[jrep] = irep;
}
else {
parent[irep] = jrep;
rank[jrep]++;
}
}
static void Main() {
int size = 5;
DisjointSet ds = new DisjointSet(size);
ds.UnionByRank(0, 1);
ds.UnionByRank(2, 3);
ds.UnionByRank(1, 3);
for (int i = 0; i < size; i++) {
Console.WriteLine("Element " + i + " belongs to the set with representative " + ds.Find(i));
}
}
}
|
Javascript
unionbyrank(i, j) {
let irep = this.find(i);
let jrep = this.find(j);
if (irep === jrep) {
return;
}
let irank = this.rank[irep];
let jrank = this.rank[jrep];
if (irank < jrank) {
this.parent[irep] = jrep;
} else if (jrank < irank) {
this.parent[jrep] = irep;
} else {
this.parent[irep] = jrep;
this.rank[jrep]++;
}
|
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++
#include <bits/stdc++.h>
using namespace std;
void unionBySize(int i, int j) {
int irep = find(i);
int jrep = find(j);
if (irep == jrep)
return;
int isize = Size[irep];
int jsize = Size[jrep];
if (isize < jsize) {
Parent[irep] = jrep;
Size[jrep] += Size[irep];
}
else {
Parent[jrep] = irep;
Size[irep] += Size[jrep];
}
}
|
Java
import java.util.Arrays;
class UnionFind {
private int[] Parent;
private int[] Size;
public UnionFind(int n)
{
Parent = new int[n];
for (int i = 0; i < n; i++) {
Parent[i] = i;
}
Size = new int[n];
Arrays.fill(Size, 1);
}
public int find(int i)
{
if (Parent[i] != i) {
Parent[i] = find(Parent[i]);
}
return Parent[i];
}
public void unionBySize(int i, int j)
{
int irep = find(i);
int jrep = find(j);
if (irep == jrep)
return;
int isize = Size[irep];
int jsize = Size[jrep];
if (isize < jsize) {
Parent[irep] = jrep;
Size[jrep] += Size[irep];
}
else {
Parent[jrep] = irep;
Size[irep] += Size[jrep];
}
}
}
public class GFG {
public static void main(String[] args)
{
int n = 5;
UnionFind unionFind = new UnionFind(n);
unionFind.unionBySize(0, 1);
unionFind.unionBySize(2, 3);
unionFind.unionBySize(0, 4);
for (int i = 0; i < n; i++) {
System.out.println("Element " + i
+ ": Representative = "
+ unionFind.find(i));
}
}
}
|
Python3
class UnionFind:
def __init__(self, n):
self.Parent = list(range(n))
self.Size = [1] * n
def find(self, i):
if self.Parent[i] != i:
self.Parent[i] = self.find(self.Parent[i])
return self.Parent[i]
def unionBySize(self, i, j):
irep = self.find(i)
jrep = self.find(j)
if irep == jrep:
return
isize = self.Size[irep]
jsize = self.Size[jrep]
if isize < jsize:
self.Parent[irep] = jrep
self.Size[jrep] += self.Size[irep]
else:
self.Parent[jrep] = irep
self.Size[irep] += self.Size[jrep]
n = 5
unionFind = UnionFind(n)
unionFind.unionBySize(0, 1)
unionFind.unionBySize(2, 3)
unionFind.unionBySize(0, 4)
for i in range(n):
print("Element {}: Representative = {}".format(i, unionFind.find(i)))
|
C#
using System;
class UnionFind
{
private int[] Parent;
private int[] Size;
public UnionFind(int n)
{
Parent = new int[n];
for (int i = 0; i < n; i++)
{
Parent[i] = i;
}
Size = new int[n];
for (int i = 0; i < n; i++)
{
Size[i] = 1;
}
}
public int Find(int i)
{
if (Parent[i] != i)
{
Parent[i] = Find(Parent[i]);
}
return Parent[i];
}
public void UnionBySize(int i, int j)
{
int irep = Find(i);
int jrep = Find(j);
if (irep == jrep)
return;
int isize = Size[irep];
int jsize = Size[jrep];
if (isize < jsize)
{
Parent[irep] = jrep;
Size[jrep] += Size[irep];
}
else
{
Parent[jrep] = irep;
Size[irep] += Size[jrep];
}
}
}
class Program
{
static void Main()
{
int n = 5;
UnionFind unionFind = new UnionFind(n);
unionFind.UnionBySize(0, 1);
unionFind.UnionBySize(2, 3);
unionFind.UnionBySize(0, 4);
for (int i = 0; i < n; i++)
{
Console.WriteLine($"Element {i}: Representative = {unionFind.Find(i)}");
}
}
}
|
Javascript
unionbysize(i, j) {
let irep = this.find(i);
let jrep = this.find(j);
if (irep === jrep) {
return;
}
let isize = this.size[irep];
let jsize = this.size[jrep];
if (isize < jsize) {
this.parent[irep] = jrep;
this.size[jrep] += this.size[irep];
} else {
this.parent[jrep] = irep;
this.size[irep] += this.size[jrep];
if (isize === jsize) {
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++
#include <bits/stdc++.h>
using namespace std;
class DisjSet {
int *rank, *parent, n;
public:
DisjSet(int n)
{
rank = new int[n];
parent = new int[n];
this->n = n;
makeSet();
}
void makeSet()
{
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x)
{
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void Union(int x, int y)
{
int xset = find(x);
int yset = find(y);
if (xset == yset)
return;
if (rank[xset] < rank[yset]) {
parent[xset] = yset;
}
else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
}
else {
parent[yset] = xset;
rank[xset] = rank[xset] + 1;
}
}
};
int main()
{
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
import java.io.*;
import java.util.*;
class DisjointUnionSets {
int[] rank, parent;
int n;
public DisjointUnionSets(int n)
{
rank = new int[n];
parent = new int[n];
this.n = n;
makeSet();
}
void makeSet()
{
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x)
{
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int x, int y)
{
int xRoot = find(x), yRoot = find(y);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[yRoot] < rank[xRoot])
parent[yRoot] = xRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
}
}
public class Main {
public static void main(String[] args)
{
int n = 5;
DisjointUnionSets dus =
new DisjointUnionSets(n);
dus.union(0, 2);
dus.union(4, 2);
dus.union(3, 1);
if (dus.find(4) == dus.find(0))
System.out.println("Yes");
else
System.out.println("No");
if (dus.find(1) == dus.find(0))
System.out.println("Yes");
else
System.out.println("No");
}
}
|
Python3
class DisjSet:
def __init__(self, n):
self.rank = [1] * n
self.parent = [i for i in range(n)]
def find(self, x):
if (self.parent[x] != x):
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def Union(self, x, y):
xset = self.find(x)
yset = self.find(y)
if xset == yset:
return
if self.rank[xset] < self.rank[yset]:
self.parent[xset] = yset
elif self.rank[xset] > self.rank[yset]:
self.parent[yset] = xset
else:
self.parent[yset] = xset
self.rank[xset] = self.rank[xset] + 1
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')
|
C#
using System;
class DisjointUnionSets
{
int[] rank, parent;
int n;
public DisjointUnionSets(int n)
{
rank = new int[n];
parent = new int[n];
this.n = n;
makeSet();
}
public void makeSet()
{
for (int i = 0; i < n; i++)
{
parent[i] = i;
}
}
public int find(int x)
{
if (parent[x] != x)
{
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y)
{
int xRoot = find(x), yRoot = find(y);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[yRoot] < rank[xRoot])
parent[yRoot] = xRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
}
}
class GFG
{
public static void Main(String[] args)
{
int n = 5;
DisjointUnionSets dus =
new DisjointUnionSets(n);
dus.union(0, 2);
dus.union(4, 2);
dus.union(3, 1);
if (dus.find(4) == dus.find(0))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
if (dus.find(1) == dus.find(0))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
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;
}
}
}
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");
}
|
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...