Disjoint Sets | Disjoint set operations in daa

Disjoint Sets Introduction

  1. A tree is used to represent each set and the root to name a set.
  2. Each node points upwards to its parent
  3. Two sets A and B are said to be disjoint if A – B = f. i.e., there is no common element in both A and B
  4. A collection of disjoint sets is called a disjoint set forest
  5. An array can be used to store parent of each element

Let  Σ = { S1  , S2 , …, Sk  }  be a collection of dynamic disjoint-sets of the elements and let x and y be any two elements. We want to support:

Make-Set(x):  create a set containing x

Find(x): return which set x belongs

Union(x, y): merge the sets containing x and containing y into one


n=11, 4 sets
s1 = {1,7,10,11} ,  s2 = {2,3,5,6},  s3 = {4,8} and s4 = {9}

Disjoint set operations in daa

Two important operations performed on disjoint sets are:

  1. Union
  2. Find

Disjoint set operations Union

  1. If S1 and S2 are two disjoint sets, their union S1 U S2 is a set of all elements x such that x is in either S1 or S2
  2. As the sets should be disjoint S1 U S2 replaces S1 and S2 which no longer exist
  3. Union is achieved by simply making one of the trees as a subtree of other i.e to set parent field of one of the roots of the trees to other root

Disjoint Sets

Disjoint Sets

Disjoint Sets:

Set Representation:

  1. An array can be used to store parent of each element
  2. The ith element of this array represents the tree node that contains the element I and it gives the parent of that element
  3. Root node has a parent -1
  4. An array P[1:n] can be taken for all n elements in the forest
  5. Element at the root node is taken as the name of the set

Example: n=11, 4 sets S1 = {1, 7, 10, 11}, S2 = {2, 3, 5, 6}, S3 = {4, 8} and S4 = {9}

UNION FIND Algorithms


Algorithm SimpleUnion(i,j)
P[i] := j;


Algorithm SimpleFind(i)
while( P[i] >= 0) do
i := P[i];
return I;


In a worst-case scenario SimpleUnion() and SimpleFind() perform badly. Suppose we start with the single element sets {1},{2},…,{n} , then, execute the following sequence of unions and finds UNION(1,2), UNION(2,3),…,UNION(n 1,n)

This sequence results in a skewed tree

Time complexity for 1 union = 1
Time complexity for n-1 union = n-1
Therefore Tall unions = O(n)
Time complexity for 1 find = i
Time complexity for n find = 1+2+….+ n-1 + n = n(n+1)/2
Therefore Tall finds = O(n2)

Disjoint set operations Weighted Union

  1. Simple Union leads to high time complexity in some cases
  2. Weighted union is a modified union algorithm with weighting rule
  3. Widely used to analyze the time complexity of an algorithm in average case
  4. Weighted union deals with making the smaller tree a subtree of the larger
  5. If the no.of nodes in the tree with root i is less than the no.of nodes in the tree with root j, then make j the parent of I, otherwise make i the parent of j
  6. Count of nodes can be placed as a negative number in the P[i] value of the root i
temp := P[i] + P[j]; // P[i]:=-count(i), P[j]:=-count(j) if(P[i]>P[j]) then
P[i] := j;
P[j] := temp;
P[j] := i;
P[i] := temp;

Collapsing Find

  1. SimpleFind() leads to high time complexity in some cases
  2. CollapsingFind() is a modified version of SimpleFind()
  3. If j is a node on the path from i to its parent and P[i]!= root, then set j to root
Algorithm CollapsingFind(i)
r := i;
while (P[r] >0) do
r := P[i];
while(i!=r) do
j := P[i];
P[i] := r;
i := j;
return r;


Topic : Disjoint Sets | Disjoint set operations in daa

This Post Has 2 Comments

  1. venkatesh chepuri


  2. Mohammad Umar

    Thank you so much. This is an excellent work. Accuracy can be improved more.

Leave a Reply