Union-Find (Disjoint Set)

The one question it answers, and why BFS isn't good enough

You already know how to find connected components with BFS or DFS: one sweep, O(V + E). That works when the graph is fixed. Union-Find exists for the other case — when edges keep arriving and you have to answer "are u and v connected?" interleaved with "now connect u and v." Re-running DFS after every edge is O(E) per query; union-find answers both operations in effectively O(1), amortized, forever.

The representation is a forest: every element points at a parent, and the root of each tree is that set's canonical name. Two elements are in the same set exactly when they reach the same root. That's the entire data structure — an array of integers.

The naive version, so you can see what breaks

class NaiveDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // everyone starts as their own root
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // walk up to the root
    return x;
  }

  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;  // already together — the return value is the useful part
    this.parent[ra] = rb;         // hang one root under the other, arbitrarily
    return true;
  }
}

This is correct and it is also a trap: union(0,1), union(1,2), union(2,3), … builds a single chain of length n, and every find then costs O(n). The two optimizations below exist purely to make the trees short — they do not change what the structure means.

The two optimizations that change the complexity class

Path compression — while walking to the root, re-point everything you passed directly at the root. You already paid to walk the path; flattening it is free.

// recursive, two-pass: the clean version to write on a whiteboard
find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]); // re-parent on the way back down
  }
  return this.parent[x];
}

// iterative, no stack depth risk — prefer this for n in the hundreds of thousands
find(x) {
  let root = x;
  while (this.parent[root] !== root) root = this.parent[root];
  while (this.parent[x] !== root) {        // second pass: hook every node on the path to root
    const next = this.parent[x];
    this.parent[x] = root;
    x = next;
  }
  return root;
}

Union by size (or rank) — when merging, always hang the smaller tree under the larger root. A node's depth only increases when its tree is absorbed by one at least as big, so a node can be pushed down at most log n times before its tree contains all n elements. That alone caps height at O(log n), even with no path compression at all.

union(a, b) {
  let ra = this.find(a), rb = this.find(b);
  if (ra === rb) return false;
  if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // ra is now the LARGER root
  this.parent[rb] = ra;
  this.size[ra] += this.size[rb];
  return true;
}

The production DSU — memorize this one

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n; // every successful union drops this by exactly one
  }

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

  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;                       // false === "these were already connected"
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }

  connected(a, b) { return this.find(a) === this.find(b); }
  setSize(x) { return this.size[this.find(x)]; }        // size is only meaningful at a root
}

Three details earn their keep in interviews: union returning a boolean (that single value solves cycle detection and Redundant Connection), the components counter (solves "number of provinces" with no extra pass), and setSize going through find first (reading size[x] on a non-root is stale garbage).

Why the combination is nearly O(1) — the intuition

With both optimizations, m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. You don't need the proof, you need the shape of the argument and a number.

• Union by size alone caps tree height at log n: a node only gets deeper when its tree is swallowed by one at least as large, so its containing set at least doubles each time — that can happen at most log₂ n times.
• Path compression alone means each expensive walk permanently destroys the structure that made it expensive. You cannot pay for the same long path twice; the cost amortizes across the sequence of operations, not per operation.
• Together, the trees flatten faster than they can grow. The rigorous bound is α(n), the inverse of a function that grows so violently that α(n) ≤ 4 for any n you can physically store — n = 2⁶⁵⁵³⁶ still gives α = 5.

Number of connected components — the counter does the work

// LeetCode "Number of Connected Components in an Undirected Graph" / "Number of Provinces"
function countComponents(n, edges) {
  const dsu = new DSU(n);
  for (const [u, v] of edges) dsu.union(u, v);
  return dsu.components;
}

// Same idea on an adjacency MATRIX (Number of Provinces) — only scan the upper triangle
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const dsu = new DSU(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) dsu.union(i, j);
    }
  }
  return dsu.components;
}

A grid problem like "Number of Islands" can be done this way too — map cell (r, c) to index r * cols + c and union each land cell with its right and down neighbours only (left/up are covered by the other cell's turn). BFS is simpler there and equally fast; reach for DSU on grids when the islands change, as in "Number of Islands II," where each added land cell is one union and the running count is free.

Cycle detection and Redundant Connection

In an undirected graph, an edge (u, v) closes a cycle exactly when u and v are already in the same set. That is precisely the case where union returns false — so cycle detection is one if.

// Does this undirected edge list contain a cycle?
function hasCycle(n, edges) {
  const dsu = new DSU(n);
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return true; // both endpoints already connected → this edge closes a loop
  }
  return false;
}

// Redundant Connection: n nodes, n edges, 1-indexed. Return the LAST edge that creates a cycle.
function findRedundantConnection(edges) {
  const dsu = new DSU(edges.length + 1); // +1 because nodes are 1-indexed; slot 0 is unused
  for (const [u, v] of edges) {
    if (!dsu.union(u, v)) return [u, v]; // edges are given in order, so the first failure IS the last-added cycle edge
  }
  return [];
}

// Bonus: "Graph Valid Tree" — a tree is exactly (n-1 edges) + (no cycle)
function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const dsu = new DSU(n);
  for (const [u, v] of edges) if (!dsu.union(u, v)) return false;
  return true; // n-1 edges and no cycle forces connectivity — no need to check it separately
}

Accounts Merge — union-find on things that aren't integers

DSU indexes integers, so the real work in most "merge these groups" problems is the mapping layer: assign each distinct string an integer id, union, then bucket by root. This is the pattern for Accounts Merge, "Sentence Similarity II," "Synonymous Sentences," and every merge-duplicates question.

// accounts[i] = [name, email1, email2, ...]. Merge accounts sharing any email.
function accountsMerge(accounts) {
  const emailToId = new Map();
  const emailToName = new Map();
  let nextId = 0;

  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, nextId++);
      emailToName.set(email, name);
    }
  }

  const dsu = new DSU(nextId);
  for (const account of accounts) {
    const firstId = emailToId.get(account[1]);
    for (let i = 2; i < account.length; i++) {
      dsu.union(firstId, emailToId.get(account[i])); // chain every email to the account's first email
    }
  }

  const groups = new Map(); // root id → list of emails
  for (const [email, id] of emailToId) {
    const root = dsu.find(id);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(email);
  }

  const result = [];
  for (const emails of groups.values()) {
    emails.sort();
    result.push([emailToName.get(emails[0]), ...emails]); // any email in the group maps to the same name
  }
  return result;
}

Complexity is O(E · α + E log E), where E is the total number of emails — the sort at the end dominates, which is worth saying out loud because it shows you costed the whole solution, not just the clever part.

The advanced aside: union-find with rollback

DSU has no split — you cannot un-merge two sets in general. But you can undo unions in reverse order if you keep a journal, which is enough for divide-and-conquer over time ("offline dynamic connectivity": each edge exists during an interval of queries, so you add it going down a segment-tree recursion and roll it back coming up).

class RollbackDSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.history = []; // journal of [childRoot, parentRoot] merges
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // NO path compression — it isn't undoable
    return x;
  }

  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) { this.history.push(null); return false; } // record a no-op so undo() stays aligned
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.history.push([rb, ra]);
    return true;
  }

  undo() {
    const entry = this.history.pop();
    if (!entry) return;
    const [child, root] = entry;
    this.parent[child] = child;      // exactly one pointer changed, so exactly one is restored
    this.size[root] -= this.size[child];
  }
}

The trade: dropping path compression costs you α and buys back O(log n) per operation from union-by-size alone — a fair price for undo. You almost certainly won't have to write this in an interview, but naming it when asked "what if edges could also be removed?" is exactly the kind of answer that separates candidates.

One more forward reference: the next chapter, Minimum Spanning Tree, is essentially this data structure plus a sort. Kruskal's algorithm is "sort all edges by weight, then add each edge whose union returns true" — the boolean you already have is precisely the "does this edge connect two different components?" test the algorithm needs.

See the chain flatten

Watch what path compression actually rewrites. The find that flattens the chain is doing the work that makes every later find cheap.

Recognizing it in an unseen problem

• The words "connected," "groups," "merge," "same network," "provinces," "friend circles," "accounts belonging to one person." Anything that is an equivalence relation (reflexive, symmetric, transitive) is a union-find problem.
• Edges arrive over time, or the question is asked repeatedly. One BFS answers one snapshot; DSU answers a stream. If you see "after each query, report the number of components," DSU is almost forced.
• Brute force would be: re-run DFS/BFS after every edge — O(E) per edge, O(E²) total. DSU makes it O(E · α).
• Distinguish from BFS/DFS: if the graph is static and you also need paths, distances, or an ordering, use traversal — DSU knows nothing about distance, path, or direction. It only answers "same set?"
• Distinguish from topological sort: DSU is undirected only. Directed dependencies, cycle detection in a DAG, ordering → topological sort.
• Pitfalls: forgetting find before reading size; sizing the array wrong on 1-indexed inputs; and comparing roots with parent[a] === parent[b] instead of find(a) === find(b) — the second is the only correct test.