Disjoint Set Union

DSU Basics

Disjoint Set Union (DSU) maintains a collection of disjoint sets. Supports: Find(x) - returns representative of x's set; Union(x,y) - merges sets containing x and y. Initially each element in its own set.

Path Compression

During Find, make every node on path point directly to root. Next Find on any of them is O(1). Without: tree height can be O(n). With: amortized α(n) ≈ 4.

Union by Rank/Size

Attach shorter tree under taller tree. Rank ≈ upper bound on height. Alternative: track size, attach smaller under larger. Both guarantee O(log n) height without path compression, O(α(n)) with.

Applications

1. Cycle detection in undirected graph: Union edge endpoints; if same root, cycle.
2. Kruskal's MST: Sort edges by weight, add if Union succeeds.
3. Connected components: After all unions, count unique roots.
4. Dynamic connectivity: Online connectivity queries with union/find.
5. Percolation: Grid cells, connect open neighbors.
6. Equation satisfaction: x=y and x!=y constraints (use 2-SAT style with extra nodes).