Disjoint Set (Union-Find)
Tracks which group each element belongs to under merging. With path compression and union by rank, find and union are effectively O(1) — the engine inside Kruskal's MST.
Union-Find maintains a partition of elements into disjoint sets, supporting two operations: find(x) returns the representative of x's set, and union(x, y) merges two sets. Each set is a tree of parent pointers; the root is the representative.
Two tiny optimisations make it astonishingly fast. Union by rank attaches the shorter tree under the taller. Path compression makes every node visited by find point directly at the root, flattening the tree for all future queries. Together they bring the amortised cost to the inverse Ackermann function α(n) — at most 4 for any conceivable input, effectively constant.
It answers dynamic connectivity: "are a and b in the same group after these merges?" Kruskal's MST uses it to detect cycles, network code uses it for connected components, and image processing uses it for region labelling.
Operations
| Operation | Complexity |
|---|---|
| find (compressed) | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
| connected(a, b) | O(α(n)) |
| space | O(n) |
Where it's used
Kruskal's algorithm, dynamic connectivity, image segmentation, percolation, deduplicating equivalent items.