# 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:

Union:

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

Find:

``````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)
FIND(1),FIND(2),…,FIND(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)

## 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
``````WeightedUnion(i,j)
{
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;
}
else
{
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;
}``````