Union-find (a disjoint-set forest) keeps elements in non-overlapping sets. Every element points at a parent, and each tree’s root, which points at itself, names its set. find(x) climbs to the root; union(a, b) hangs one root under the other; two elements are connected exactly when their roots match. Two tricks keep the trees flat: union by rank hangs the shorter tree under the taller one, and path compression points every element a find passes straight at the root.
- Typical operation
- O(α(n))
- Space
- O(n)