Union-Find (Disjoint Set)

MNEMONIC Find the boss, link the bosses.

THE PATTERN A forest of representative roots

Union-Find (a.k.a. Disjoint Set Union) maintains a partition of n elements into disjoint sets. It is stored as a forest: a single parent[] array where a root points to itself and every other node points one step toward its root.

Two operations drive everything. find(x) returns the representative root of x's set by following parent pointers. union(x, y) merges the two sets by linking one root under the other. From these you get connectivity queries and a live component count, computed onlineas edges arrive — no need to see the whole graph first.

KEY IDEA Representative root + two optimizations

The unlock is the representative root: collapse a whole set to a single canonical element, so “same set?” reduces to “same root?”. Two optimizations keep the trees flat, and they compound:

• Path compression (in find): re-point every node visited directly at the root, so future lookups are one hop.
• Union by rank / size (in union): hang the shorter (or smaller) tree under the taller (or larger) one, so depth grows as slowly as possible.

COST Complexity at a glance

Space is O(n) for the parent (and rank/size) arrays.

VARIANTS Count components · detect the cycle edge

• Count connected components. Initialize components = n and decrement on each successful union; the leftover count is the answer. (Or count self-pointing roots at the end.)
• Detect the cycle-forming edge. Process edges in order; if union(u, v) returns false, then u and v already share a root — this edge closes a cycle (Redundant Connection).
• Validate a tree. A graph on n nodes is a tree iff it has exactly n − 1 edges and no union ever returns false (no cycle).

RUN IT Find the boss, link the bosses

1class UnionFind {
2  parent: number[];
3  rank: number[];
4  components: number;
5 
6▶  constructor(n: number) {
7▶    this.parent = Array.from({ length: n }, (_, i) => i); // self-root
8▶    this.rank = new Array(n).fill(0);
9    this.components = n;
10  }
11 
12  find(x: number): number {
13    if (this.parent[x] !== x)
14      this.parent[x] = this.find(this.parent[x]); // path compression
15    return this.parent[x];
16  }
17 
18  union(x: number, y: number): boolean {
19    const rx = this.find(x), ry = this.find(y);
20    if (rx === ry) return false;                  // already merged → cycle
21    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
22    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
23    else { this.parent[ry] = rx; this.rank[rx]++; }
24    this.components--;
25    return true;
26  }
27}

TRIGGERS When you see ___ → reach for ___

Reach for Union-Find when the problem is about grouping by connectivity and edges arrive incrementally — you only need to know which set things end up in, not the route between them.

RED FLAGSWhen it's NOT this pattern

• You need the actual shortest path, the distance, or the route itself. Union-Find only tells you whether two nodes share a component, never the path between them. Use BFS (unweighted) or Dijkstra (weighted) instead.
• Edges get removedover time. Standard DSU only supports merging, not splitting — deletions need a different structure (e.g. offline / rollback DSU) or a rebuild.
• You must enumerate or order the members of each group / traverse them.That is a traversal job — reach for DFS/BFS component labelling, which can also yield the count.

TEMPLATE DSU class — path compression + union by rank

When → The reusable core. Drop this in whenever a problem is about connectivity or grouping. union returns false when the two endpoints are already merged, which is exactly the hook cycle-detection problems need.

class UnionFind {
  private parent: number[];
  private rank: number[];
  public components: number;

  constructor(n: number) {
    // Each element starts in its own set, pointing at itself.
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }

  // Return the representative root of x, compressing the path on the way up.
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // PATH COMPRESSION
    }
    return this.parent[x];
  }

  // Merge the sets of x and y. Returns false if they were already merged.
  union(x: number, y: number): boolean {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;                  // same set already

    // UNION BY RANK — hang the shorter tree under the taller one.
    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]++;                            // tie → root grows by one
    }
    this.components--;
    return true;
  }

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

TEMPLATE Count connected components

When → Anytime the answer is “how many groups remain after adding all the edges.” Track the live count instead of doing a second pass over the roots.

// Number of connected components in an undirected graph.
function countComponents(n: number, edges: [number, number][]): number {
  const uf = new UnionFind(n);   // start with n separate components
  for (const [u, v] of edges) {
    uf.union(u, v);              // each SUCCESSFUL merge drops the count by 1
  }
  return uf.components;          // (equivalently: count i where find(i) === i)
}

TEMPLATE Cycle detection — first edge that closes a cycle

When → Redundant Connection and “is this a valid tree”. Iterate edges in order; the first edge whose union returns false is the one joining two already-connected nodes.

// Redundant Connection — the first edge that closes a cycle.
function findRedundantConnection(edges: [number, number][]): [number, number] {
  const uf = new UnionFind(edges.length + 1); // nodes are 1..n
  for (const [u, v] of edges) {
    // union returns false ⇒ u and v already share a root ⇒ this edge makes a cycle.
    if (!uf.union(u, v)) return [u, v];
  }
  return [-1, -1]; // unreachable when a redundant edge is guaranteed to exist
}

PITFALL Forgetting path compression → TLE

Without compression (or union by rank), the forest can degenerate into a single long chain and each find becomes O(n). On large inputs this is the difference between passing and timing out. The one line parent[x] = find(parent[x]) inside find is not optional in practice.

PITFALL Skipping union by rank / size

Linking roots arbitrarily lets trees grow tall. Always attach the shorter/smaller tree under the taller/larger one (track rank or size per root). On a tie, pick either root and bump its rank by one.

PITFALL "Already unioned" (cycle) vs a fresh merge

When find(x) === find(y), the edge is redundant — it closes a cycle and must not change the component count. Only a union of two distinct roots is a real merge. Returning a boolean from union (false = already merged) makes both the cycle test and the count bookkeeping fall out cleanly.

PITFALL 0- vs 1-indexed nodes

Mixing labelling conventions is a classic off-by-one. If the input uses nodes 1..n, size the arrays at n + 1; if it uses 0..n−1, size them at n. Initialize parent[i] = i for every valid index.

PROBLEMS