Union-Find (Disjoint Set Union) tracks a partition of elements into disjoint sets and supports two near-O(1) operations: find (which set is x in?) and union (merge two sets). It excels at connectivity queries.
The idea
Each set is a tree with a representative root. With and , operations run in nearly constant time (inverse Ackermann, α(n)).
