Union-Find

You look after a small office network of six computers, numbered 0 to 5. All day, someone plugs in a new cable between two of them. In between, people ask you things like "can computer 5 talk to computer 1 yet?"

You could answer each question with a BFS or DFS from computer 5. That works, but it walks the whole network every time. With 100,000 computers and 100,000 questions, that is billions of steps. You do not need paths here. You only need to know which group each computer is in, and to merge two groups when a cable joins them. A union-find structure does exactly that, and each operation takes only a few steps.

#The idea: every group has a boss

Each group picks one member to be its root, like a team captain. Every computer stores one number: its parent, the computer it reports to. A root reports to itself. At the start, nobody is connected, so everyone is their own root.

That gives you two operations:

• find(x): follow parent pointers from x until you reach a computer that is its own parent. That is the root of x's group. Two computers are connected exactly when they have the same root.
• union(a, b): find the root of each. If the roots differ, make one root report to the other. One pointer change merges two whole groups.

Notice that union never touches the other members. Everyone who reported to the old root still does, and the old root now reports to the new one, so their find still ends at the right place, just one hop later.

#Trace it on six computers

The array is parent: cell i holds the parent of computer i. The arrows in the picture point from each computer to its parent. Each root also keeps a size: how many computers are in its group.

find(x):  if parent[x] != x: parent[x] = find(parent[x])  return parent[x]union(a, b):  ra, rb = find(a), find(b)  if ra == rb: return false  if size[ra] < size[rb]: swap ra, rb  parent[rb] = ra; size[ra] += size[rb]

#Two tricks that keep trees flat

The whole cost of union-find is the walk inside find. A short walk means fast operations. Without care, the walks get long.

Suppose you always put the first root under the second, and the cables arrive as 0–1, 1–2, 2–3, 3–4. Each union hangs the whole existing group under one new computer. You get a chain, and find(0) walks past every computer. With n computers that is n steps per find, no better than searching the graph.

Union by size. Always hang the smaller group's root under the bigger group's root. A computer only gets one hop further from its root when its group joins a group at least as big, so its group at least doubles each time. A group of n can only double about log₂ n times, so no walk is longer than log₂ n hops. For a million computers, that is 20.

Path compression. Every time find walks up a path, point every computer on it straight at the root. You did the walk anyway, so this costs nothing extra, and the next find from any of them takes one hop.

#The code

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // everyone is their own root
    this.size = new Array(n).fill(1);
    this.groups = n;
  }
 
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
 
  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA === rootB) return false; // already in the same group
    if (this.size[rootA] < this.size[rootB]) [rootA, rootB] = [rootB, rootA];
    this.parent[rootB] = rootA; // smaller tree goes under the bigger one
    this.size[rootA] += this.size[rootB];
    this.groups--;
    return true;
  }
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # everyone is their own root
        self.size = [1] * n
        self.groups = n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False  # already in the same group
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a  # smaller tree goes under the bigger one
        self.size[root_a] += self.size[root_b]
        self.groups -= 1
        return True

To ask "are a and b connected?", compare find(a) with find(b). The groups counter tells you how many separate pieces the network is in, without any search. It drops by one only when a union really merges two groups.

The return value of union is useful on its own. When it returns false, the two computers were already connected, so the new cable closes a loop. That is how you detect a cycle in an undirected graph while reading its edges one at a time, and it is the heart of Kruskal's algorithm in Minimum Spanning Trees.

"Amortized" means averaged over a long run of operations. One find can still take a few hops, but it flattens the path it walked, so later finds are cheaper.

#Common mistakes

#Check yourself

#What to practise next

Union-find returns in Minimum Spanning Trees, where it decides which cheap cables are worth laying. First, though, graphs get weights: Dijkstra's Algorithm finds the fastest route when every road has a travel time.