What is the disjoint-set data structure?

The disjoint-set data structure (union-find structure) keeps track of sets that are partitioned into non-overlapping subsets. This disjoint-set structure can be implemented using:

• Arrays
• Trees

Methods

1. Union(a,b): This function takes two indexes and merges their root nodes if they have not been previously merged.
2. Find(a,b): This function checks if​ two indexes lie in the same set or in two different sets.
3. makeSet(a): This function makes a new set with the specified element.

Illustration

Since we are left with the two disjoint sets given below, we can use the array to find out if the two indexes lie in the same set or in ​two different sets. If the two indexes have the same parent, then they lie in the same set; otherwise, they are in disjoint sets.