union-find for Kruskal's algorithm

Kruskal's algorithm asks the same question thousands of times: 'are these two towns already in the same connected piece of my network?' If yes, the cable between them would make a wasteful loop and should be skipped. You need a way to answer that question, and to merge two pieces when you do add a cable, both blindingly fast. Union-find is the tiny data structure built for exactly this, and nothing else.

Union-find maintains a collection of disjoint sets and supports two operations: find(x) returns a representative element identifying x's set, and union(x, y) merges the two sets containing x and y. It is stored as a forest: each element points to a parent, and the root of each tree is the set's representative. Two vertices are in the same set exactly when find walks them up to the same root. Two optimizations make it astonishingly fast. Union by rank attaches the shorter tree under the taller one so trees stay shallow. Path compression makes every node visited during a find point straight to the root afterward, flattening the tree for next time. Together they give an amortized cost per operation of O(alpha(n)), where alpha is the inverse Ackermann function — effectively a small constant (below 5) for any n that could ever arise.

In Kruskal's, each edge triggers one find on each endpoint (same root means same component, so reject the edge) and, when the edge is accepted, one union to merge the components. Because each of these is amortized near-constant, the whole connectivity bookkeeping costs about O(E alpha(V)), which is dwarfed by the O(E log E) edge sort — so union-find is essentially free relative to the sort. Two honest notes: alpha(n) is amortized, meaning the average over a sequence is tiny, though a single find can still walk a longer path; and basic union-find supports merging and querying but not splitting sets back apart, which is why it fits Kruskal's add-only process perfectly but not problems that delete edges.