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 in the same set or not.

Approach

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

  • How to determine the root/representative of a set? Unionizing 2 elements by bigger index or by higher rank.

Implementation

  • Find with compress path and Union by bigger index

Initial state of parents

Final state of parents after all unionizing

  • Find with compress path and Union by higher rank

Initial state of parents

Final state of parents after all unionizing