jsschools

Union-Find (Disjoint Set Union)

A data structure that efficiently tracks a partition of elements into disjoint sets, supporting near-O(1) union and find operations via path compression and union by rank.

Spec ↗

Syntax

class UnionFind {
  constructor(n) { this.parent = Array.from({length:n},(_,i)=>i); this.rank = new Array(n).fill(0); }
  find(x) { ... }   // with path compression
  union(x, y) { ... } // with union by rank
}

Parameters

NameTypeRequiredDescription
n number Yes The number of elements (0 to n-1) in the initial partition.

Returns

UnionFind — A new Union-Find structure with n singleton sets.

Examples

class UnionFind {
  #parent; #rank;
  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#rank   = new Array(n).fill(0);
  }
  find(x) {
    if (this.#parent[x] !== x) this.#parent[x] = this.find(this.#parent[x]); // path compression
    return this.#parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    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]++; }
    return true;
  }
  connected(x, y) { return this.find(x) === this.find(y); }
}

const uf = new UnionFind(6);
uf.union(0, 1); uf.union(1, 2); uf.union(3, 4);
console.log(uf.connected(0, 2)); // same set
console.log(uf.connected(0, 3)); // different sets
Output 
true
false

// Kruskal's MST uses Union-Find to detect cycles
function kruskal(V, edges) {
  edges.sort((a, b) => a[2] - b[2]); // sort by weight
  const uf = new UnionFind(V);
  let cost = 0, edgeCount = 0;
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) { cost += w; edgeCount++; }
    if (edgeCount === V - 1) break;
  }
  return cost;
}
// 4 vertices: 0-1 (1), 0-2 (4), 1-2 (2), 1-3 (5), 2-3 (1)
const edges = [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,1]];
console.log(kruskal(4, edges));
Output 
4

Notes

| Operation | Time | Space | |----------|---------------|-------| | Find | O(α(n)) ≈ O(1)| O(n) | | Union | O(α(n)) ≈ O(1)| O(1) | | Connected| O(α(n)) ≈ O(1)| O(1) | α(n) is the inverse Ackermann function — effectively constant for all practical n. Path compression flattens trees on each find; union by rank keeps trees shallow. Together they achieve near-O(1) amortized per operation. Classic uses: Kruskal's MST, detecting cycles, counting connected components, network connectivity.

See also