Union-Find (Disjoint Sets)

The 10-second versionCopy Anchor Link

Union-Find tracks a pile of elements split into groups. Two operations: find(x) tells you which group x is in, and union(x, y) merges two groups into one. The trick is to store each group as a little tree of parent pointers — the root is the group's name — and then to cheat gravity with two cheap moves: always attach the shallower tree under the deeper one (union by rank), and flatten the path as you walk it (path compression). Together they make both operations run in amortized O(α(n)) time, where α is the inverse Ackermann function — a number that never exceeds 4 for any input that fits in the universe.

Why this existedCopy Anchor Link

The story starts inside a compiler, during the rise of ALGOL in the early 1960s. A compiler has to decide whether two names refer to the same thing — two variable references that are really one variable, two types that are really one type — and it has to do it transitively: if A and B are the same and B and C are the same, then A and C are the same, forever.

Bernard Galler and Michael Fischer attacked exactly this in their 1964 paper "An improved equivalence algorithm", and built the structure we now call union-find. It answered a question that had nothing to do with graphs: "which equivalence class is this thing in?"

Then the theorists fell in love with it and sharpened it for decades. In 1975, Robert Tarjan proved that adding path compression drops the amortized cost to O(α(n)), and in 1984 Tarjan and Jan van Leeuwen nailed down the tight analysis of combining it with union by rank. The result is one of the most astonishing results in algorithms: an operation so close to constant time that it is, for all practical purposes, O(1).

Why it mattered then: before union-find, merging two big groups meant relabelling every element in one of them, and a long chain of merges cost quadratic time. Union-find turned the same work into something close to free — which is why it quietly underpins minimum spanning trees, network connectivity and physics simulations to this day.

Inside the inventor's headCopy Anchor Link

The naive version is easy to state and easy to break. Keep the elements in a plain array, one label per element. find(x) is a lookup, O(1). But union has to pick a winning label and relabel every element of the losing group — and if you merge a million-element group into a one-element group, you just rewrote a million entries for one edge.

So Galler and Fischer tried a different idea: don't relabel anything. Represent each group as a tree, where every element points to its parent, and the element that points to itself is the root — the group's name. Now:

• find(x) means walk up to the root. No relabelling, just a climb.
• union(x, y) means make one root point at the other. One pointer change.

That's beautiful — until it isn't. Watch the trap. If you always attach the first tree under the second, a run of unions can lay the elements out in a straight chain:

// Naive find: walk to the root. Fine — until the tree becomes a long chain.function findNaive(parent, x) {  while (parent[x] !== x) x = parent[x];  return x;}// Naive union: always hang the first tree under the second root.// union(0,1); union(1,2); union(2,3); ...  builds a straight line of length n.function unionNaive(parent, a, b) {  parent[findNaive(parent, a)] = findNaive(parent, b);}

Feed it union(0,1), union(1,2), union(2,3), … and the "tree" becomes 0 → 1 → 2 → 3 → …, a linked list in disguise. Now find(0) walks the entire chain — O(n). You've traded the naive relabelling disaster for a climbing disaster.

Two separate fixes land here, and together they're the whole magic:

Union by rank stops the chain from forming: when merging, hang the shorter tree under the taller one, so no path grows unless both sides are already tall. Path compression cleans up after the fact: whenever find(x) climbs to the root, re-point every node it passed directly at the root, so future climbs are one hop. Neither alone is enough to be "free"; together they are α(n). That combination — one structural rule and one lazy-but-greedy shortcut — is the aha.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

The invariants that make it correctCopy Anchor Link

1. Roots point at themselves. parent[x] == x identifies a root. It's the base case of every find.
2. Same group ⇔ same root. Two elements are connected exactly when find(x) == find(y) — the root is the group's identity, no matter the shape of the tree below it.
3. Rank bounds the height. rank[r] is an upper bound on the height of the tree rooted at r. Attaching a lower-rank root under a higher-rank one never increases the taller height, so heights grow only logarithmically.
4. Path compression never changes which tree you're in. Flattening a path keeps every node pointing to the same root — it only shortens the route. Correctness is untouched; only the walk gets faster.
5. The parent array is finite and loop-free. Every union joins two distinct roots, so the structure is always a forest of trees — never a cycle.

A worked traceCopy Anchor Link

Start with six lone elements. The parent array begins as [0,1,2,3,4,5] — everyone their own root. Now do five unions and watch the array change:

After the last union, 3 still points at 2 and 5 still points at 4, so find(3) walks 3 → 2 → 0 and find(5) walks 5 → 4 → 0 — but both now compress, leaving 3 and 5 pointing straight at 0. Every subsequent query on those elements is one hop. The group of six is now a single root, 0, with a perfectly flat tree underneath.

It in codeCopy Anchor Link

One array, two careful methods. This is the complete, production-shaped structure:

class UnionFind {  constructor(n) {    this.parent = Array.from({ length: n }, (_, i) => i);    this.rank = new Array(n).fill(0);  }  find(x) {    while (this.parent[x] !== x) {      this.parent[x] = this.parent[this.parent[x]];  // path halving      x = this.parent[x];    }    return x;  }  union(a, b) {    let ra = this.find(a), rb = this.find(b);    if (ra === rb) return;    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];    this.parent[rb] = ra;                        // attach shorter tree under taller    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;  }}

Cost tableCopy Anchor Link

α(n) is the inverse Ackermann function, and it grows so absurdly slowly that it's at most 4 for every n smaller than the number of atoms in the observable universe. "Inverse Ackermann" sounds terrifying; in practice it means constant. Space is a simple O(n): one parent slot and one rank slot per element.

Where you meet it todayCopy Anchor Link

• Kruskal's minimum spanning tree. Sort the edges, and use union-find to skip any edge whose endpoints are already connected — it's the entire "would this form a cycle?" check, and it's the next page.
• Dynamic connectivity. Networks where links come and go ("are these two machines on the same subnet?") ask union-find questions constantly.
• Percolation and physics. "Does water reach the bottom of this grid?" is a union of adjacent open cells, checked once at the end — a famous Monte-Carlo simulation.
• Image segmentation and clustering. Grow regions by merging neighbouring pixels that look alike; each merge is a union.

The connectivity query is the clearest one. Counting the connected components of an undirected graph is just "start with n groups, and decrement every time a union actually merges two":

// Number of connected components: start at n, drop by one per real merge.function countComponents(n, edges) {  const uf = new UnionFind(n);  let comps = n;  for (const [a, b] of edges) {    if (uf.find(a) !== uf.find(b)) {      uf.union(a, b);                           // merged two groups      comps--;    }  }  return comps;}

RecapCopy Anchor Link

• Union-Find maintains a set of disjoint groups with two operations: find (which group?) and union (merge two groups).
• Groups are trees of parent pointers; the root (a self-pointer) is the group's name.
• Union by rank keeps trees shallow; path compression flattens them as you walk. Together: amortized O(α(n)), effectively O(1).
• It was born in a 1960s compiler for equivalence classes, then sharpened by Tarjan and van Leeuwen.
• You meet it in Kruskal's MST, percolation, dynamic connectivity and image segmentation.

Next up: Minimum Spanning Trees — where union-find becomes the beating heart of a greedy algorithm.