Union Find: The Structure That Only Answers "Same Group?"

Most graph questions are secretly two different questions wearing the same coat.

"Is there a path from A to B?" wants the path. You need traversal — BFS, DFS, Dijkstra — because the answer is a sequence of edges.

"Are A and B in the same group?" does not want the path. It wants one bit. And if you answer it with a traversal, you pay for a path you throw away.

Union Find (Disjoint Set Union, DSU) is the structure that answers only the second question. Everything it is good at, and every way it will let you down, follows from that one restriction.

Here is what the difference costs. Redundant Connection: a tree on N nodes plus one extra edge, find the edge that closes the cycle. Feed both approaches the worst input — a path 1-2-3-...-N with [1, N] tacked on the end — and time them.

Measured on Node v22.22.3, Linux aarch64, both implementations in this article, answers verified identical. The DFS column quadruples every time N doubles, which is what O(N^2) looks like on a stopwatch. The DSU column does not really move — at this size it is still mostly warm-up noise.

The array, and nothing else

DSU is one integer array. parent[i] is the node you are told to ask instead. Follow the chain until a node points at itself; that node is the root, and the root's identity is the group's identity.

class NaiveDSU {
  parent: number[];
 
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
 
  find(x: number): number {
    while (this.parent[x] !== x) x = this.parent[x];
    return x;
  }
 
  union(a: number, b: number): boolean {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false; // already together
    this.parent[rootB] = rootA;
    return true;
  }
}

That is a complete, correct DSU. It is also slow, and the interesting part is how slow, because the answer depends entirely on the order you hand it edges.

Measure the tree before you optimise it

find costs one array read per level. So the only number that matters is the height of the tallest tree. I built four variants — no heuristics, path compression only, union by rank only, both — and walked every node to its root to get the true height.

Adversarial order. 100,000 nodes, union(i, i - 1) for i in 1..99999, so each new node arrives as the first argument and its singleton root swallows the existing tree:

Random order. 100,000 random unions over 100,000 nodes:

Two things in there are worth stopping on.

Path compression alone did nothing in the adversarial run. That is not a bug in the measurement. Compression only flattens a path you actually walk, and in that build order every find lands on a root or a singleton, so no long path is ever traversed. The tree is 99,999 deep and stays that way until someone finally queries a leaf. Path compression is a repair, not a prevention.

Union by rank is the prevention, and it is doing most of the work. Compression's job is to keep the already-short trees short as queries pile up: at N = 1,000,000 the combination holds max height at 4 and average depth at 1.130, essentially unchanged from N = 1,000 (height 3, depth 1.095). That flatness is what "practically constant" means.

The textbook bound for both heuristics together is O(m · α(n)) amortised, where α is the inverse Ackermann function — Tarjan proved it in 1975 ("Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2)). I have not verified that proof and neither have you. What I did verify is the table above: the height stops growing. Quote the bound if an interviewer asks, but the measurement is the part you can defend.

Same three unions — union(1,0), union(2,1), union(3,2) — same final grouping, very different shape. Arrows point at parents, the direction find walks.

Path compression is the second pass. Walk to the root, then walk the chain again and repoint every node straight at it:

The implementation

Note rank starts at 0. A singleton has height 0, and rank is meant to bound the height — starting it at 1 leaves every rank in the array off by one against its own definition. It does not change behaviour, but it will confuse you at 2am.

class UnionFind {
  private parent: number[];
  private rank: number[];
  public count: number;
 
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array<number>(size).fill(0);
    this.count = size; // every node starts as its own component
  }
 
  find(x: number): number {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    // second pass: repoint everything on the path straight at the root
    while (this.parent[x] !== root) {
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }
 
  union(a: number, b: number): boolean {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false;
 
    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA] += 1; // only a tie can grow the tree
    }
    this.count -= 1;
    return true;
  }
 
  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

find is a loop, not recursion. Almost every DSU article you will read writes the recursive one-liner instead:

// don't ship this one
function findRecursive(parent: number[], x: number): number {
  if (parent[x] !== x) parent[x] = findRecursive(parent, parent[x]);
  return parent[x];
}

The same trap is in the naive solution people write first. A recursive DFS-per-edge on a 8,000-node path graph does not run slowly — it throws RangeError before it finishes. "10,000 nodes means 100 million operations" is the optimistic version of what happens.

Three problems

Redundant Connection (LeetCode 684). Union each edge in order; the first union that returns false is the answer. Because the input is a tree plus exactly one edge, the first edge that closes a cycle is also the last edge of that cycle in input order, which is what the problem asks for.

function findRedundantConnection(edges: number[][]): number[] {
  const dsu = new UnionFind(edges.length + 1);
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v];
  }
  return [];
}

Number of Connected Components (LeetCode 323). 0-indexed, so new UnionFind(n) exactly. The count field does the work:

function countComponents(n: number, edges: number[][]): number {
  const dsu = new UnionFind(n);
  for (const [u, v] of edges) dsu.union(u, v);
  return dsu.count;
}

Self-loops and duplicate edges are handled for free: union returns false and count is untouched.

Accounts Merge (LeetCode 721). DSU indexes an array, so strings need a numbering layer first. Assign every distinct email an id, union each account's emails to its first email, then bucket by root.

function accountsMerge(accounts: string[][]): string[][] {
  const emailToId = new Map<string, number>();
  const emailToName = new Map<string, string>();
 
  for (const account of accounts) {
    const name = account[0];
    for (let i = 1; i < account.length; i++) {
      const email = account[i];
      if (!emailToId.has(email)) emailToId.set(email, emailToId.size);
      emailToName.set(email, name);
    }
  }
 
  const dsu = new UnionFind(emailToId.size);
  for (const account of accounts) {
    for (let i = 2; i < account.length; i++) {
      dsu.union(emailToId.get(account[1])!, emailToId.get(account[i])!);
    }
  }
 
  const groups = new Map<number, string[]>();
  for (const [email, id] of emailToId) {
    const root = dsu.find(id);
    const bucket = groups.get(root);
    if (bucket) bucket.push(email);
    else groups.set(root, [email]);
  }
 
  const merged: string[][] = [];
  for (const emails of groups.values()) {
    emails.sort();
    merged.push([emailToName.get(emails[0])!, ...emails]);
  }
  return merged;
}

The inner loop starts at i = 2 and unions against account[1], so an account with a single email creates no unions and still shows up as its own group. Transitivity is free: if account 1 links a-b and account 2 links b-c, a and c land in the same bucket without anyone comparing them.

Where it stops working

Three limits worth knowing before you reach for it:

• No deletion. Path compression destroys the tree's history. Once nodes have been repointed at the root you cannot undo a union, and there is no cheap fix — the standard workaround is to process the whole edge sequence backwards so deletions become insertions.
• No path. DSU can tell you edge [1,4] closes a cycle. It cannot tell you which nodes are on that cycle. If the follow-up question is "return the cycle", you are doing a traversal anyway.
• Groups only, not structure. Bipartiteness, distance, direction — all of it is gone. There are DSU variants that carry extra state (weighted DSU for ratios, a doubled array for bipartite checking), but plain DSU has thrown that information away by design.

Run it yourself

console.assert does not throw in Node, so a broken file still prints a green line. Use something that actually fails:

const assert = (cond: boolean, msg: string): void => {
  if (!cond) throw new Error(msg);
};
 
const eq = (a: unknown, b: unknown, msg: string): void =>
  assert(JSON.stringify(a) === JSON.stringify(b), `${msg}: got ${JSON.stringify(a)}`);
 
// the naive version is correct, just tall
const naive = new NaiveDSU(4);
[[1, 0], [2, 1], [3, 2]].forEach(([a, b]) => naive.union(a, b));
eq(naive.parent, [1, 2, 3, 3], "NaiveDSU builds a chain on this order");
assert(naive.find(0) === 3, "chain still resolves to one root");
 
// core structure
const uf = new UnionFind(6);
assert(uf.count === 6, "six singletons");
assert(uf.union(0, 1) === true, "first union merges");
assert(uf.union(1, 0) === false, "second union is a no-op");
assert(uf.count === 5, "count only drops on a real merge");
assert(uf.connected(0, 1) && !uf.connected(0, 2), "connectivity");
 
// LeetCode 684
eq(findRedundantConnection([[1, 2], [1, 3], [2, 3]]), [2, 3], "684 ex1");
eq(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]), [1, 4], "684 ex2");
eq(findRedundantConnection([]), [], "684 empty");
eq(findRedundantConnection([[1, 1]]), [1, 1], "684 self-loop");
eq(findRedundantConnection([[1, 2], [1, 2]]), [1, 2], "684 duplicate edge");
 
// LeetCode 323
assert(countComponents(5, [[0, 1], [1, 2], [3, 4]]) === 2, "323 ex1");
assert(countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) === 1, "323 ex2");
assert(countComponents(1, []) === 1, "323 single node");
assert(countComponents(0, []) === 0, "323 no nodes");
assert(countComponents(3, [[0, 0], [1, 1]]) === 3, "323 self-loops only");
 
// LeetCode 721
eq(
  accountsMerge([["A", "a@x.com", "b@x.com"], ["A", "b@x.com", "c@x.com"]]),
  [["A", "a@x.com", "b@x.com", "c@x.com"]],
  "721 transitive merge"
);
eq(accountsMerge([]), [], "721 empty");
 
console.log("all assertions passed");

Beyond those cases I ran the class against a brute-force oracle: 8,000 random graphs (up to 40 nodes, self-loops and duplicate edges included), 162,998 unions, 200,000 connected(a, b) queries, plus 4,000 randomly generated tree-plus-one-edge graphs for 684. Component counts matched BFS labelling every time, and every 684 answer, once removed, left a spanning tree.

Check yourself

Option 3. This is the adversarial row in the first table: height 99,999 on 100,000 nodes, identical with and without compression. But be careful which union sequence you cite as the example — with parent[rootB] = rootA, calling union(1,2), union(2,3), union(3,4), ... builds a star of height 1, not a chain, because find has already collapsed the second argument to a root. I measured it: 100,000 nodes, no rank, no compression, height 1. Reverse the arguments to union(i+1, i) and you get the 99,999-deep chain. The orientation of your own union decides which input is the bad one.

Option 3, and the tie is the only case that increments anything. When ranks differ, the shorter tree slots in beneath the taller one and the height genuinely does not change, so the rank must not either. Increment on every union and rank stops tracking height, which quietly turns the heuristic off.

The one-line version

If you can answer the question with "same root or not", use Union Find. If you need to say anything about how they are connected, you were always going to traverse. The measurements above are the whole argument: 4 levels at a million nodes, or 99,999 at a hundred thousand, and the only thing separating them is which root you attach to which.