Imagine a room of people forming friend groups. Two questions come up constantly: "are these two in the same group?" and "merge these two groups." Union-Find — also called Disjoint Set Union (DSU) — answers both in effectively constant time, without ever listing group members.

The trick is that each element only needs to remember a parent. Follow parents upward and you reach a representative (the root) that names the whole set. Two elements are in the same set exactly when they share a root — so both queries reduce to "walk to the root and compare."

The two operations

find(x) walks parent pointers up to the root of x. union(a, b) finds both roots and, if they differ, points one root at the other — stitching two trees into one. Everything the structure does is built from these two.

Making it fast — two optimizations

A naive DSU can degrade into a long chain, making find O(n). Two cheap tweaks fix that. Union by rank always hangs the shorter tree under the taller one, keeping trees bushy. Path compression flattens the path during find by re-pointing every node you pass directly at the root, so the next lookup is instant.

Why "near-O(1)"

With both optimizations, m operations run in O(m · α(n)), where α is the inverse Ackermann function. For any input that fits in the observable universe, α(n) < 5 — so it is constant time in every practical sense, but not literally O(1).

A clean JS implementation

DSU with path compression + union by rank

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.rank = new Array(n).fill(0)
    this.count = n // number of disjoint sets
  }

  find(x) {
    // path compression: re-point x straight at its root
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }

  union(a, b) {
    let ra = this.find(a)
    let rb = this.find(b)
    if (ra === rb) return false // already connected

    // union by rank: hang the shorter tree under the taller
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra]
    this.parent[rb] = ra
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++
    this.count--
    return true
  }

  connected(a, b) {
    return this.find(a) === this.find(b)
  }
}

Operation	Time

α is the inverse Ackermann function — effectively a small constant (< 5) for all real inputs.

Where you actually use it

DSU is the quiet workhorse behind any problem about "grouping" or "connectivity" where you only ever merge sets, never split them.

Connected components — union every edge, then count is the number of components.
Cycle detection in an undirected graph — if union(u, v) returns false (already connected), that edge closes a cycle.
Kruskal's MST — sort edges by weight and add each one unless it would form a cycle; DSU is exactly the cycle test.
Grid problems — number of islands, percolation, and "accounts merge" style clustering.

One-way street

Union-Find merges sets but cannot un-merge them. If a problem deletes edges or splits groups over time, DSU alone will not do — you need a different approach (e.g. offline processing in reverse, or a link-cut tree).

Takeaway

When a problem is about who is connected to whom and only ever adds connections, reach for DSU: two tiny operations, near-constant time, and a handful of lines of code.

Union-Find (Disjoint Set Union)

The two operations

Making it fast — two optimizations

A clean JS implementation

Where you actually use it

Section navigation