Union-Find
AlgorithmsDisjoint Set Union — near-O(1) 'are these connected?' and 'merge these groups'.
Definition
Union-Find (Disjoint Set Union) tracks a partition of elements into disjoint sets with two operations: find(x) returns a representative for x's set, and union(x, y) merges two sets. With path compression and union by rank/size, both run in near-constant amortized time (inverse Ackermann).
When to use
Reach for it on dynamic connectivity — counting connected components, detecting a cycle in an undirected graph, and Kruskal's minimum spanning tree. It shines when edges arrive incrementally and you keep asking 'are these two already linked?'.