A social network asks the same question millions of times: are these two people connected? Not directly, necessarily — connected through some chain of friendships, groups, and bridges.
Answering with a graph search means walking the graph every time. If the graph is also changing constantly, that search becomes a tax on every operation.
Union-find answers a narrower question, and answers it in near-constant time: which component is this item in?
Every item belongs to exactly one set, and each set has a representative: a single root that names the whole group.
Ask find(x) and it returns the representative of x’s set. Ask union(a, b) and it merges the sets containing a and b. If find(a) and find(b) return the same representative, the two are already connected. If not, union connects them.
This is the disjoint-set union structure, usually called union-find. It stores no edges. It cannot report the path between two items. It maintains only a partition of the world into non-overlapping groups.
The narrowness is the point. When the question is connectivity under merges, union-find reduces the problem to two operations and makes both nearly free.
In 1964 Bernard Galler and Michael Fischer described an improved algorithm for equivalence relations. Their representation is trees of parent pointers: each item points toward a root, and the root names the set.
A decade later Robert Tarjan proved the running time. With two small optimizations, m operations on n items run in O(m α(n)), where α is the inverse Ackermann function — a function that grows so slowly the difference from constant has never mattered in practice.
The underlying relation is equivalence. If a is equivalent to b, and b to c, then a is equivalent to c. Connections spread by transitivity.
Graphs make it concrete. Adding an edge merges two components; later, a query asks whether two vertices sit in the same one. For a graph that only gains edges, union-find processes every merge and every query without traversing the graph again.
One parent pointer per item. Initially every item is its own parent, so every item is a set of size one.
To find an item’s representative, follow parent pointers until you reach a root — a node whose parent is itself. To union two items, find both roots; if they differ, point one root at the other. A single pointer write merges two entire sets.
Suppose 9 points to 4, 4 points to 2, and 2 points to itself. Then find(9) walks 9 → 4 → 2 and returns 2.
That root is the set’s representative. Every item that climbs to 2 belongs to the same set. Which item happens to be root does not matter; it is a stable answer shared by the whole component.
To union(9, 6), find the root of 9 and the root of 6. If both are already 2, nothing happens: they are connected.
If one root is 2 and the other is 8, point one root at the other. Everything that used to climb to 2 now climbs through 2 to 8. One parent pointer changes the representative of an entire component.
The naive version has a failure mode. If every union attaches the first root beneath the second, an unlucky sequence builds a chain: 1 under 2, 2 under 3, 3 under 4, and onward.
find(1) now walks the whole chain. The answers stay correct while the running time quietly becomes linear. Union-find depends on those parent-pointer trees staying shallow.
The first fix: when two roots merge, attach the shallower tree beneath the deeper one. Union by size — attaching the smaller beneath the larger — gives the same bound.
Chains can no longer form. A tree’s rank increases only when it absorbs a tree of equal rank, which at least doubles its size, so rank grows logarithmically in the number of nodes.
The second fix happens inside find. After walking from a node to the root, point every node on that path directly at the root.
The first find pays for the climb and flattens the path behind it. Later finds skip the middle entirely. Queries leave the structure in better shape than they found it: every search is also a small repair.
Union-find merges sets and tests whether two items currently share one. It does not split sets. Once two components are unioned, the merge is permanent.
That restriction is what makes it fast. A graph that only gains edges is exactly union-find’s case. A graph that loses edges, so components can split apart, needs a heavier dynamic connectivity structure.
With union by rank and path compression together, m operations on n items take O(m α(n)) time, where α is the inverse Ackermann function.
The Ackermann function grows explosively, so its inverse grows the other way. For any n that fits in a machine, α(n) is at most 4. In real code union-find is constant time with a footnote nobody has ever had to read.
One parent array, one rank array, two operations. find climbs and compresses. union finds both roots and attaches the shallower beneath the deeper.
Roughly forty lines of code. That is the entire structure, and it is hard to beat whenever the problem really is: merge groups, then ask whether two things ended up in the same one.
Kruskal’s minimum spanning tree algorithm sorts the edges by weight and scans them cheapest first.
For each edge, ask union-find whether its endpoints are already connected. If they are, the edge would close a cycle, so skip it. If not, keep the edge and union the components. Cycle detection becomes a pair of finds.
In a binary image, neighbouring foreground pixels belong to the same component. Scanning the image, union the provisional labels of adjacent pixels whenever they turn out to describe the same blob.
At the end every label compresses to its representative. Many provisional names collapse into connected components: letters on a page, islands in a mask, regions in a segmentation pass.
Deduplication has the same shape. If one record shares an email with a second, and the second shares a phone number with a third, all three may describe the same entity.
Each matching fact is a union. When the facts are exhausted, each root names one merged account, cluster, or equivalence class. The structure never needed to know why two records matched — only to preserve the transitive consequences.
Union-find forgets how components joined. It can report that two nodes are connected but not the path between them. It merges, and it never unmerges.
Rollback variants exist for offline algorithms, and dynamic connectivity structures handle deletion, but the core stays deliberately narrow. It is not a graph database. It is a component labeller with unusually cheap bookkeeping.
Network connectivity. Percolation simulations. Type unification in compilers. Connected-component labelling. Minimum spanning trees. Clustering. Account merging.
Each has the same shape: start with separate things, discover reasons to treat some of them as the same, then repeatedly ask whether two names now refer to one group.
Watch a path collapse. The first query climbs through several ancestors. The next query on the same node reaches the root in one step.
The structure gets faster exactly where it is used. Work done once becomes speed later, and repeated questions flatten the forest toward something close to a two-level tree.
A forest of parent pointers, one rank hint per root, and a find operation that tidies up behind itself. Merges are permanent, paths are unavailable, and the answers arrive in α(n) time.
The speed comes from what union-find declines to know. It does not model edges, paths, or history — only sameness, which is all its callers ever ask about.