Union-Find

Seven people. Every so often two of them become friends. At any moment you might be asked: are these two in the same friendship group?

Groups only ever merge — friendships are never broken. That one restriction is what makes a very fast answer possible.

The obvious way

Store the friendships as a graph, and answer each question with a traversal: walk out from A and see whether you reach B.

That is $O(V + E)$ per question. Fine once. Asked a million times on a graph that keeps growing, it is hopeless — and notice that most of the work is repeated, because the group memberships barely change between questions.

The realisation

Do not store who is friends with whom. Store, for each person, one arrow pointing at somebody else in their group.

Follow the arrows and you eventually reach someone who points at themselves. That person is the group’s leader, and two people are in the same group exactly when they reach the same leader.

• find(x) — follow arrows from x until you reach the leader.
• union(a, b) — find both leaders; if they differ, point one at the other.

That is the whole structure. Six merges, watch the arrows form:

The naive version, and why it degrades

class DSU {
  private parent: number[];

  constructor(n: number) {
    // Everyone starts as their own leader: n groups of one.
    this.parent = Array.from({length: n}, (_, i) => i);
  }

  find(x: number): number {
    while (this.parent[x] !== x) x = this.parent[x]!;
    return x;
  }

  union(a: number, b: number): void {
    this.parent[this.find(b)] = this.find(a);
  }
}

Correct, and it can be terrible. Run union(0,1), union(1,2), union(2,3), … and each merge hangs the new leader off the end of a growing chain. After $n$ merges you have a linked list, and find is $O(n)$ — no better than the traversal we were trying to avoid.

Both fixes below exist to stop that chain forming.

Fix one: path compression

After a find walks the chain, it already knows the leader. So on the way back out, point every node it passed straight at that leader:

find(x: number): number {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]!);   // relink on the way back
  }
  return this.parent[x]!;
}

Three characters of change, and the effect is large: a chain is walked at most once, because afterwards everything on it is one hop from the leader. The structure is repaired by the act of querying it.

Fix two: union by size

Path compression alone still allows a bad chain to be built, since union picks arbitrarily. So make it pick deliberately: hang the smaller group under the larger one.

union(a: number, b: number): boolean {
  let ra = this.find(a);
  let rb = this.find(b);
  if (ra === rb) return false;             // already together

  // Smaller tree hangs off the bigger one, so depth grows as slowly as possible.
  if (this.size[ra]! < this.size[rb]!) [ra, rb] = [rb, ra];
  this.parent[rb] = ra;
  this.size[ra]! += this.size[rb]!;
  return true;
}

A node’s depth only increases when its group is absorbed by a bigger one, which means the group it belongs to at least doubles. Doubling can only happen $\log_2 n$ times, so depth stays under $\log_2 n$ even without compression.

What it costs

With both fixes, $m$ operations on $n$ elements take $O(m \cdot \alpha(n))$, where $\alpha$ is the inverse Ackermann function.

That function grows so slowly that $\alpha(n) \le 4$ for any $n$ that fits in this universe — the number of atoms in the observable universe is around $10^{80}$, and $\alpha(10^{80})$ is 4. So in practice it is constant time, and saying “effectively $O(1)$” is honest.

It is not actually constant, though, and the proof that it is $\alpha$ rather than $\log$ is famously one of the hardest results in elementary algorithm analysis.

Where you meet it

Kruskal’s minimum spanning tree. Sort the edges cheapest first; take an edge if and only if it joins two different groups. That test is one union call, and false means “this edge would make a cycle, skip it”.

Connected components. Union every edge, then count the elements that are their own leader.

Grid flood-fill without recursion. Treat each cell as an element and union neighbours that match — commonly the “number of islands” problem, and it handles a stream of new land that a traversal would have to redo from scratch.

Cycle detection while building. Adding an edge between two nodes that already share a leader closes a cycle.