Union-Find (Disjoint Set Union)

Build a union-find structure with path compression and union by rank for near-constant-time component queries, and apply it to connected components, cycle detection, and Kruskal's MST.

5 min read Level 3/5 #dsa#graph#union-find

What you'll learn

Implement union-find with path compression and union by rank
Explain why the amortised complexity is nearly O(1) per operation
Apply union-find to detect cycles in undirected graphs and count connected components

Union-Find (also called Disjoint Set Union, DSU) is a data structure that tracks a partition of elements into disjoint sets and supports two operations: find (which set contains this element?) and union (merge two sets). With path compression and union by rank, both operations run in amortised O(alpha(n)) time — practically O(1) for any realistic input size.

Core Implementation

class UnionFind {
  constructor(n) {
    // Each element starts as its own root
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank   = new Array(n).fill(0);
    this.components = n;
  }

  // Path compression: flatten the tree as we walk up
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Union by rank: attach smaller tree under larger tree
  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false; // already same component

    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }
    this.components--;
    return true;
  }

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

Path Compression Visualised

Without path compression, repeated find calls on a chain of 6 nodes walk the entire chain each time. After the first call with compression, every node points directly to the root:

Before:  1 → 2 → 3 → 4 → 5 → 6 (root)
After:   1 → 6,  2 → 6,  3 → 6,  4 → 6,  5 → 6

Use Case 1 — Connected Components

function countComponents(numVertices, edges) {
  const uf = new UnionFind(numVertices);
  for (const [u, v] of edges) uf.union(u, v);
  return uf.components;
}

console.log(countComponents(5, [[0,1],[1,2],[3,4]])); // 2

Use Case 2 — Cycle Detection in Undirected Graphs

function hasCycle(numVertices, edges) {
  const uf = new UnionFind(numVertices);
  for (const [u, v] of edges) {
    if (!uf.union(u, v)) return true; // already same component → cycle
  }
  return false;
}

console.log(hasCycle(4, [[0,1],[1,2],[2,3],[3,0]])); // true
console.log(hasCycle(3, [[0,1],[1,2]]));              // false

Complexity

Operation	Amortised time	Space
find	O(alpha(n)) ≈ O(1)	O(n)
union	O(alpha(n)) ≈ O(1)	O(n)
connected	O(alpha(n)) ≈ O(1)	O(n)

alpha(n) is the inverse Ackermann function, which is at most 4 for any input you will ever encounter in practice.

Up Next

With graphs fully covered, explore trie data structures for efficient prefix lookups and autocomplete.

Trie Introduction →