Union-Find

AlgorithmsMid priority~1 h

Disjoint Set Union — near-O(1) 'are these connected?' and 'merge these groups'.

Definition

Union-Find (Disjoint Set Union) tracks a partition of elements into disjoint sets with two operations: find(x) returns a representative for x's set, and union(x, y) merges two sets. With path compression and union by rank/size, both run in near-constant amortized time (inverse Ackermann). See Graphs for how it compares to BFS/DFS as a connectivity tool — this page covers the structure itself, its two optimizations, and a full worked example.

When to use

Reach for it on dynamic connectivity — counting connected components, detecting a cycle in an undirected graph, and Kruskal's minimum spanning tree. It shines when edges arrive incrementally and you keep asking 'are these two already linked?'.

Techniques

Path compression — every time find(x) walks up to the root, re-point every node it passed directly at that root. Future find calls on those nodes become O(1). Without it, a chain of unions can degrade find to O(n).

Union by rank / size — when merging two sets, attach the smaller tree under the larger tree's root (tracked by a size or rank array), instead of picking arbitrarily. This keeps trees shallow on its own, even without path compression. The two optimizations together are what give the near-constant inverse Ackermann bound — either alone is only logarithmic.

Component counting — keep a running counter, decremented once per successful union (a union that actually merges two different roots). A union between elements already in the same set must be a no-op that leaves the counter untouched.

Related concepts

Union-Find answers the same 'are these connected?' question BFS and DFS do, but incrementally and near-O(1) per query instead of O(V+E) per full traversal — the trade is that it can't recover which path connects two elements, only whether one exists. See Graphs for where it fits (Kruskal's MST, cycle detection) alongside the rest of the toolkit.

Implementation

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);  // everyone starts as their own root
    this.size = new Array(n).fill(1);
    this.count = n;                                       // number of disjoint sets
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);          // path compression: point straight at the root
    }
    return this.parent[x];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false;                    // already connected — no-op
    const [small, big] = this.size[rootA] < this.size[rootB] ? [rootA, rootB] : [rootB, rootA];
    this.parent[small] = big;                             // attach the smaller tree under the larger
    this.size[big] += this.size[small];
    this.count--;
    return true;
  }
}

Disjoint Set Union with both optimizations — find compresses paths, union attaches by size.

Worked examples

Number of Provinces — given an n × n adjacency matrix of directly-connected cities, count the number of provinces (groups of cities reachable from each other, directly or transitively). Scan the upper triangle of the matrix once, unioning every directly-connected pair; the final component count is the answer.

isConnected — city 0 and 1 are directly linked; city 2 is on its own

	0	1	2
0	1	1	0
1	1	1	0
2	0	0	1

scanning the matrix's upper triangle, unioning every directly-connected pair

start: parent = [0,1,2], provinces = 3

Every city begins as its own root — three separate provinces.

i↓

j↓

isConnected[0][1] = 1 → union(0,1)

Cities 0 and 1 are directly connected. Merge their sets: provinces drops to 2.

i↓

j↓

isConnected[0][2] = 0 → skip

0 and 2 aren't directly connected — no union.

i↓

j↓

isConnected[1][2] = 0 → skip, scan done

1 and 2 aren't connected either. Two roots remain — {0,1} and {2} — so the answer is 2.

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {                     // upper triangle only — matrix is symmetric
      if (isConnected[i][j] === 1) uf.union(i, j);
    }
  }
  return uf.count;
}

Union every directly-connected pair; the component count left standing is the answer.

The double loop over the matrix is O(n²), dominating the near-O(1)-per-call union/find work — compare this to a BFS/DFS solution, which would also be O(n²) here (the matrix itself is the input size) but re-derive each component from scratch rather than updating incrementally.

Things to look out for

Skip either path compression or union-by-size and you lose the near-constant bound — a naive union-find degrades to O(n) per find on an adversarial sequence of unions (a long chain).
find must walk all the way to the true root, not just check the immediate parent — a node's parent pointer isn't always the root until path compression has run.
If the elements aren't already dense integers 0..n-1 (account names, arbitrary strings), build an index map first — the array-backed parent/size structure needs that normalization.

Corner cases

n = 0 or n = 1 — 0 or 1 component, no unions possible.
No edges at all — every element stays its own root; count equals n.
A union between two elements already in the same set (a redundant edge) — must be a no-op that doesn't double-decrement the counter.
All elements eventually merge into a single set — find should still resolve in near-O(1) after path compression, not degrade as the tree grows.

Practice

Essential

Number of Provincesmedium Redundant Connectionmedium

Learning resources

NeetCode — Graphs practice setDoc Tech Interview Handbook — Graph cheatsheetArticle