Union Find

Overview

Union Find (disjoint set union, DSU) tracks which elements belong to the same group as groups merge. It supports two operations: find(x) returns the representative (root) of x's group, and union(a, b) merges the groups of a and b. With path compression and union by rank, both run in nearly O(1) amortized time.

It shines when connections arrive over time and you repeatedly ask 'are these connected?' or 'how many groups are there?' It is also the core of Kruskal's minimum spanning tree algorithm and a clean way to detect cycles in undirected graphs.

When to use it

• Dynamic connectivity: edges are added and you query whether two nodes are connected.
• Counting connected components as edges arrive.
• Detecting a cycle when adding undirected edges (redundant connection).
• Grouping equivalent items: accounts with shared emails, similar strings, equations.
• Kruskal's minimum spanning tree.

Problem patterns it solves

Where it is used in real software

Key terms

parent[x]

The node x points to; a root points to itself.

find(x)

Follow parents to the root.

Path compression

During find, point every visited node directly at the root.

Union by rank / size

Attach the smaller tree under the larger to keep trees shallow.

Inverse Ackermann alpha(n)

The amortized cost per operation; at most 4 for any practical n.

How it works, step by step

1. 1
   Initialize

   parent[i] = i and size[i] = 1 for every element. components = n.

2. 2
   find(x)

   If parent[x] !== x, set parent[x] = find(parent[x]) (path compression) and return it.

3. 3
   union(a, b)

   Find both roots. If equal, they are already connected (a cycle for edges).

4. 4
   Attach smaller under larger

   parent[smallRoot] = bigRoot; size[bigRoot] += size[smallRoot]; components--.

5. 5
   connected(a, b)

   find(a) === find(b).

684. Redundant Connection

edges = [[1,2], [1,3], [2,3]]

When both endpoints already share a root, the edge closes a cycle. Each check is nearly O(1), so processing all edges is almost linear.

Implementation

1class UnionFind {2  constructor(n) {3    this.parent = Array.from({ length: n }, (_, i) => i);4    this.size = new Array(n).fill(1);5    this.components = n;6  }7 8  find(x) {9    while (this.parent[x] !== x) {10      this.parent[x] = this.parent[this.parent[x]]; // path halving11      x = this.parent[x];12    }13    return x;14  }15 16  union(a, b) {17    let ra = this.find(a), rb = this.find(b);18    if (ra === rb) return false; // already connected19    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];20    this.parent[rb] = ra;21    this.size[ra] += this.size[rb];22    this.components--;23    return true;24  }25 26  connected(a, b) { return this.find(a) === this.find(b); }27}28 29function findRedundantConnection(edges) {30  const uf = new UnionFind(edges.length + 1);31  for (const [u, v] of edges) if (!uf.union(u, v)) return [u, v];32  return [];33}34 35// 990. Satisfiability of Equality Equations36function equationsPossible(equations) {37  const uf = new UnionFind(26);38  const id = (ch) => ch.charCodeAt(0) - 97;39  for (const e of equations) if (e[1] === "=") uf.union(id(e[0]), id(e[3]));40  return equations.every((e) => e[1] === "=" || !uf.connected(id(e[0]), id(e[3])));41}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Comparing parent[a] === parent[b] instead of roots.

  Fix: Always compare find(a) and find(b).

• Forgetting path compression.

  Fix: Without it, chains make find O(n) and solutions time out.

• Off-by-one for 1-indexed nodes.

  Fix: Allocate n + 1 slots.

Interview questions

Practice problems