Data Structureshard

What problem does Union-Find (Disjoint Set Union) solve?

Answer

Union-Find maintains disjoint sets with find(x) (representative) and union(a,b) (merge). It’s used for connectivity and Kruskal’s MST; with path compression + union by rank, operations are almost O(1) amortized.

class DSU {
  private parent: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }

  find(x: number): number {
    if (this.parent[x] === x) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(a: number, b: number) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra !== rb) this.parent[rb] = ra;
  }
}

Advanced answer

Deep dive

Union-Find (Disjoint Set Union) maintains a partition of elements into disjoint sets and supports:

find(x): return the representative of x’s set
union(a, b): merge two sets

With two optimizations:

path compression (flatten trees during find)
union by rank/size (attach smaller tree under larger)

…each operation is effectively constant for real inputs: O(alpha(n)) amortized (inverse Ackermann, grows extremely slowly).

Where it’s used

Connectivity queries in an undirected graph: are u and v connected?
Kruskal’s MST: union edges as you pick them, detect cycles via find.
Grouping / clustering problems (merge-by-constraint).

Examples

class DSU {
  private parent: number[]
  private size: number[]

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.size = Array.from({ length: n }, () => 1)
  }

  find(x: number): number {
    if (this.parent[x] === x) return x
    this.parent[x] = this.find(this.parent[x])
    return this.parent[x]
  }

  union(a: number, b: number) {
    let ra = this.find(a)
    let rb = this.find(b)
    if (ra === rb) return
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]
    this.parent[rb] = ra
    this.size[ra] += this.size[rb]
  }
}

Common pitfalls

Forgetting union by rank/size (can degrade performance).