Disjoint Sets

A disjoint set data structure contains a collection of non-overlapping sets. Various operations can be performed on the disjoint subsets which we get by partitioning the disjoint set. Operations like adding new sets, merging the sets, and also finding the representative member of a set can be performed. Also, we can find out whether the two elements are in the same set or not.

In simple words, the disjoint set can be defined as the subsets where there is no common element in the intersection of the two sets. Let’s understand this through an example.

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

1. We need to add a new friendship relation, i.e., a person x must become the friend of another person y.
2. Also, find whether the individual x is a friend of individual y (either directly or indirectly)

Let’s assume, we are given 10 individuals and we represent them as follows,

a, b, c, d, e, f, g, h, i, j

Following are the relationships which are to be added.

a <-> b  

b <-> d

c <-> f

c <-> i

j <-> e

g <-> j

And we are given a query if a is a friend of d or not.

We then need to create 4 groups and maintain a quickly accessible connection among the items of the group:

G1 = {a, b, d}

G2 = {c, f, i}

G3 = {e, g, j}

G4 = {h}

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

The solution to the problem:

We partition the individuals into different sets according to their respective groups. This method is known as a disjoint set data structure where we maintain a collection of disjoint sets and each set is represented by one of its members.

Approach to the problem:

How do we Resolve sets?

Initially, all the elements belong to different sets. We then select a member as a representative after working on the given relations. However, there can be many ways to select a representative, a simple way would be to select the one with the highest index.

Checking if 2 persons are in the same group or not? 

If two individuals have the same representative, then they’ll become friends.

What are the data Structures used?

Array: We make use of an array of integers which we call parent[]. Suppose that we are dealing with n items, the i’th element of the array represents the i’th item or keep it precise, the i’th element of the array is the parent of the i’th item. These relationships would create one or more virtual trees.

Tree: A tree is a disjoint set. Suppose that two elements are a part of the same tree, it means that they are in the same disjoint set. The root node of each tree is will be called the representative of the set. There is always a unique representative of each set. A simple rule that needs to be followed to identify the representative is if i is the representative of a set, then 

parent[i] = i. On the other hand, if i is not the representative of the set, then we can find it by traveling up the tree until we find the representative.

Operations :

Find: The find operation can be implemented by recursively traversing through the parent array until we reach a node that is the parent of itself.

Example:

Consider that we are given an element x and we have to find a set containing it.

By applying find(3), it returns the set which contains element 3 i.e., S1.

By applying find(5), it returns the set which contains element 5 i.e., S2.

Following is the algorithm for find operation:

Algorithm SimpleFind(i)

{
while( P[i] >=0) do
}
I := P[i];
}
Return I;
}

Union: It inputs two elements and finds the representatives of their sets by using the find operation. It finally puts one of the trees (representing the set) under the root node of the other tree thereby effectively merging the trees and the sets.

Example:

Let us consider that S1 and S2 are two disjoint sets and their union is the set of all elements “x” such that “x” is either is S1 or S2. AS we require disjoint sets, S1 U S2 replaces S1 and S2 which no longer exist now. We can achieve the union by simply making one of the trees a subtree of the other. 

Following is the algorithm for union operation

Algorithm SimpleUnion(i,j)

{
P[i] :=j;
}

We have reached the end of the article. In this article, we covered all about disjoint set data structure with the help of an example, operations of disjoint sets with examples, and algorithms.