What are Disjoint Sets?

Disjoint sets are sets whose intersection is the empty set. For example, {0, 1, 2} and {3} are disjoint sets, while {0, 1, 2} and {2, 3} are not.

Problem

Given some separated elements grouped in disjoint sets. Find whether 2 elements are in the same set or not.

Approach

  • How to determine if 2 elements are in the same set? Check if they have the same set root/representative.

  • How to determine the root/representative of a set? Choose the biggest index of a set or by rank.

Implementation

Find with compress path and Union by biggest index


Inital state of parents

Final state of parents

Find with compress path and Union by rank


Final state of parents

References

Disjoin-set Data Structures (topcoder.com)