JavaScript Snippet

Disjoint Set (Union-Find) Template

Difficulty: Hard

Disjoint Set Union (DSU) tracks a partition of N elements into disjoint groups, supporting near-constant-time `find` (which group?) and `union` (merge two groups). It is the building block for Kruskal's MST, connected components on dynamic graphs, and the redundant-connection problem. This snippet covers the parent-array skeleton, the path-compression optimisation that flattens trees on every find, and the union-by-rank merge that keeps trees shallow.