Tracking disjoint sets
Union find, also called a disjoint set union, maintains a collection of non overlapping sets and supports two operations: find, which returns a representative for an element's set, and union, which merges two sets. It powers Kruskal's MST, cycle detection, and dynamic connectivity.
The forest of parents
Each element points to a parent, and following parents upward leads to a root that names the set. Two elements are in the same set when they share a root. Naively these trees can grow tall and slow.
Two optimisations
- Path compression: during a find, after reaching the root, repoint every visited element directly at the root. Future finds on those elements become almost immediate.
- Union by rank or size: when merging, attach the shorter or smaller tree under the taller or larger one, keeping trees flat.
Used together, these make each operation run in almost constant amortised time, growing so slowly with input size that it is effectively flat for any practical input. This near constant behaviour is why union find is the backbone of so many graph algorithms.
Key idea
Union find stores sets as parent forests, and combining path compression with union by rank keeps the trees flat so find and union run in nearly constant amortised time.