Union-find

Union-find, also called a disjoint-set structure, keeps track of which items belong to the same group as you keep merging groups together. Each item points to a parent, and following parents upward leads to a root that acts as the group’s name, so two items are in the same group if they reach the same root. Two tricks keep it fast: attach the smaller tree under the larger when merging, and repoint items straight at the root whenever you look them up. Together they make each operation effectively constant time. It’s the tool behind Kruskal’s minimum spanning tree algorithm, finding connected components and spotting cycles in undirected graphs.