Union-Find (Disjoint Set Union)

Track dynamic group membership with near-constant-time find and union operations using path compression and union by rank.

Track dynamic group membership with near-constant-time find and union operations using path compression and union by rank.

Each element's root (representative) is the canonical group identifier; path compression ensures find reaches it in near O(1) amortised time.

Path compression flattens the tree on each find call, amortising future finds to near O(1).

Union by rank keeps trees shallow, preventing the O(n) degenerate chain that naive union produces.