Union-Find Pattern

When to use Union-Find

• The problem asks for the number of connected components, the size of the largest group, or whether two elements share a group.
• Edges arrive one at a time and you need to detect when adding one would create a cycle (Kruskal's MST, Redundant Connection).
• You need to merge sets dynamically and answer membership queries efficiently, where rebuilding the graph after every update would be too slow.
• The problem can be reframed as equivalence classes — accounts that share an email, islands that touch, friends-of-friends groups.
• An undirected graph is sparse and you want O(E * alpha(N)) instead of O(V + E) BFS/DFS, especially when edges stream in.

Template

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    const rx = this.find(x);
    const ry = this.find(y);
    if (rx === ry) return false;
    if (this.rank[rx] < this.rank[ry]) [this.parent[rx], this.parent[ry]] = [ry, rx];
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    this.count--;
    return true;
  }
}

Common mistakes

• Implementing find() without path compression, which degrades the worst-case operation cost to O(N) and causes TLE on tight time limits.
• Implementing union() without union-by-rank or union-by-size, producing chain-shaped trees that defeat path compression's amortized bound.
• Forgetting to call find() on both operands before comparing them in union() — using raw parent[x] gives the immediate parent, not the root.
• On Accounts Merge, indexing the union-find by account name rather than by a stable email-to-index map, which causes silent merges across distinct people with the same name.
• Decrementing the component count even when the two endpoints already share a root, which understates the final component count.