Union-Find

How union-find works

Each element points to a "parent." Roots point to themselves. Finding the root of an element walks up the parent chain. Two elements are in the same group if they have the same root.

• find(x): walk up x's parent chain until reaching a root.
• union(x, y): find their roots; if different, attach one under the other.

Naive implementations cost O(n) for find in the worst case (long chain). Two optimizations bring it down to O(α(n)) amortized — virtually constant.

The two optimizations that make it fast

Path compression

When you walk up the chain from x to its root, point every node along the path directly at the root. Subsequent finds for those nodes are O(1).

function find(x) {
  if (parent[x] !== x) {
    parent[x] = find(parent[x]);  // recurse, then collapse path
  }
  return parent[x];
}

Iterative version avoids recursion stack:

function find(x) {
  let root = x;
  while (parent[root] !== root) root = parent[root];
  // Second pass: compress
  while (parent[x] !== root) {
    const next = parent[x];
    parent[x] = root;
    x = next;
  }
  return root;
}

Union by rank

When merging two trees, attach the shorter under the taller. This keeps the maximum depth at O(log n) even without path compression. Rank is an upper bound on depth — incremented only when two equal-rank trees merge.

function union(x, y) {
  const rx = find(x), ry = find(y);
  if (rx === ry) return false;  // already in same group
  if (rank[rx] < rank[ry])      parent[rx] = ry;
  else if (rank[rx] > rank[ry]) parent[ry] = rx;
  else { parent[ry] = rx; rank[rx]++; }
  return true;
}

Why both optimizations together?

Optimizations	Find amortized	Union amortized	Tree height
None	O(n) worst case	O(n) worst case	O(n)
Path compression only	O(log n) amortized	O(log n) amortized	Variable
Union by rank only	O(log n) per find	O(log n) per union	O(log n)
Both	O(α(n)) amortized	O(α(n)) amortized	Effectively bounded

Either optimization alone gives O(log n). Together they multiply down to O(α(n)) — effectively O(1) — proven by Tarjan in 1975 in one of the deepest results in classical algorithm analysis.

JavaScript implementation

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.componentCount = n;
  }

  find(x) {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    // Path compression
    while (this.parent[x] !== root) {
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }

  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    // Union by rank
    if (this.rank[rx] < this.rank[ry]) {
      this.parent[rx] = ry;
    } else if (this.rank[rx] > this.rank[ry]) {
      this.parent[ry] = rx;
    } else {
      this.parent[ry] = rx;
      this.rank[rx]++;
    }
    this.componentCount--;
    return true;
  }

  connected(x, y) { return this.find(x) === this.find(y); }
}

Python implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # Path compression
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.components -= 1
        return True

Famous union-find problems

Kruskal's MST

function kruskal(n, edges) {
  // edges: [[u, v, weight], ...]
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(n);
  const mst = [];
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      mst.push([u, v, w]);
      if (mst.length === n - 1) break;
    }
  }
  return mst;
}

Sort edges by weight, take each one if it doesn't create a cycle (which union-find checks in α(n)). Total: O(m log m) for the sort + O(m α(n)) for the unions ≈ O(m log m).

Number of Islands II

Given a grid initially all water, you add land cells one at a time. After each addition, report the number of islands. Each addition unions the new land cell with up to 4 neighboring land cells. The component count from union-find is the answer. O(k α(n)) for k operations.

Accounts Merge

Given a list of accounts (each with a list of emails), merge accounts that share at least one email. Map each email to a node, union the emails in each account, then group emails by root. Linear in total emails.

When to reach for union-find

• Connectivity over a stream of edge additions. Kruskal's MST is the canonical example. Any algorithm that processes edges and asks "are these connected?" benefits.
• Connected components in image processing. Pixel grouping, region labeling, image segmentation — union neighboring pixels with similar properties.
• Equivalence classes / set partitioning. "Group these accounts by some equivalence relation." Union-find is the partition data structure.
• Cycle detection in undirected graphs. Process edges; if both endpoints already share a root, the edge would create a cycle. Faster than DFS for offline / batch processing.
• Network failure tolerance. Track which nodes are still connected as edges go down. Union-find handles additions; for deletions, link-cut trees or other dynamic structures are required.

Common union-find bugs

• Forgetting path compression. Without it, finds become O(log n) and the algorithm degrades. Always include it for production use.
• Implementing recursive find on deep trees. Path compression naturally limits depth, but during the first deep find you may stack-overflow. Use the iterative two-pass version above for safety.
• Initializing rank inconsistently. All ranks should start at 0. Initial parents must be self-references (each element is its own root in its own group).
• Returning the wrong rank semantics. Rank is NOT the exact tree depth — it's an upper bound that's easier to maintain. Don't try to use rank for anything other than the union-by-rank heuristic.
• Confusing "weight" with "rank." Some textbooks use "union by size" (count of elements) instead of rank. Both work and give the same asymptotic bound; pick one and stick with it.