‘Are these two things in the same group?’ — answered almost instantly, even as groups keep merging. Union-Find keeps each element pointing toward a representative; to check connection, follow the pointers to the root; to merge two groups, point one root at the other. With path-compression it’s so fast it’s effectively constant. It’s the engine of Kruskal’s MST and connectivity. Slide to union groups and watch them fuse.
A disjoint-set (union-find) structure maintains a partition of elements into groups, each a tree pointing to a representative ROOT. FIND(x) follows parent pointers to the root; UNION(a,b) links one root under the other; a and b are connected iff FIND(a)=FIND(b). Two optimizations — union by rank/size and PATH COMPRESSION (flatten the path to the root on each find) — give an amortized cost of O(α(n)), the inverse Ackermann function, effectively constant. It underlies [[the-minimum-spanning-tree|Kruskal’s MST]], connectivity, and image labeling. A fail-loud self-check throws unless connected elements share a root and unconnected ones don’t. ◆ real data structures, node-verified.
Near-constant O(α(n)) is amortized (with both optimizations); a naive version is slower. The connectivity semantics (find/union) are exact. It answers ‘same group?’ — not WHICH elements are in a group without extra bookkeeping.