Java Coding Problems

126. Union Find

The Union Find algorithm operates on a disjoint-set data structure.

A disjoint-set data structure defines sets of elements separated in certain disjoint subsets that are not overlapping. Graphically, we can represent a disjoint-set with three subsets, as in the following diagram:

In the code, a disjoint-set is represented as follows:

• n is the total number of elements (for example, in the preceding diagram, n is 11).
• rank is an array initialized with 0 that is useful to decide how to union two subsets with multiple elements (subsets with lower rank become children of subsets with a higher rank).
• parent is the array that allows ...