Union-Find

Union-Find (Disjoint Sets)

Written by Swapnil RajaUpdated 29 Aug 2026

Union-Find is the structure for questions about grouping. It cannot tell you the path between two nodes - only whether one exists - and that restriction is what makes it almost free.

What it does

Two operations, on a collection of disjoint groups:

find(x) - which group is x in?
union(a, b) - merge the two groups.

With both optimisations applied, each is effectively O(1) - technically inverse Ackermann, which is under 5 for any input that will ever exist.

Union-Find

javascript

class UnionFind {
  #parent
  #rank
  #groups

  constructor(size) {
    // Everything starts as its own group.
    this.#parent = Array.from({ length: size }, (_, i) => i)
    this.#rank = new Array(size).fill(0)
    this.#groups = size
  }

  find(x) {
    // Path compression: point every node straight at the root
    // on the way back, so the next find is instant.
    if (this.#parent[x] !== x) {
      this.#parent[x] = this.find(this.#parent[x])
    }
    return this.#parent[x]
  }

  union(a, b) {
    const rootA = this.find(a)
    const rootB = this.find(b)

    if (rootA === rootB) return false   // already together

    // Union by rank: hang the shorter tree off the taller one
    // so the structure stays flat.
    if (this.#rank[rootA] < this.#rank[rootB]) {
      this.#parent[rootA] = rootB
    } else if (this.#rank[rootA] > this.#rank[rootB]) {
      this.#parent[rootB] = rootA
    } else {
      this.#parent[rootB] = rootA
      this.#rank[rootA]++
    }

    this.#groups--
    return true
  }

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

const demoUf = new UnionFind(3)
demoUf.union(0, 1)
console.log(demoUf.find(0) === demoUf.find(1))  // true
console.log(demoUf.find(0) === demoUf.find(2))  // false

Both optimisations matter. Without path compression the trees grow tall and find degrades to O(n). Without union by rank you can build a straight line by merging in the wrong order.

Counting groups

Connected components

javascript

// Repeated from above so this example runs on its own.
class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i)
    this.rank = new Array(size).fill(0)
    this.groups = size
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x])
    return this.parent[x]
  }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b)
    if (ra === rb) return false
    if (this.rank[ra] < this.rank[rb]) this.parent[ra] = rb
    else if (this.rank[ra] > this.rank[rb]) this.parent[rb] = ra
    else { this.parent[rb] = ra; this.rank[ra]++ }
    this.groups--
    return true
  }
}

function countComponents(n, edges) {
  const uf = new UnionFind(n)
  for (const [a, b] of edges) uf.union(a, b)
  return uf.groups
}

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

Detecting a cycle

In an undirected graph, an edge joining two nodes already in the same group closes a cycle. union returning false is the detection.

Cycle detection

javascript

function hasCycle(n, edges) {
  const uf = new UnionFind(n)

  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return true   // already connected
  }

  return false
}

// UnionFind from earlier in this lesson.
class UnionFind {
  constructor(n) { this.owner = Array.from({ length: n }, (_, i) => i) }
  find(x) { while (this.owner[x] !== x) x = this.owner[x]; return x }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b)
    if (ra === rb) return false
    this.owner[ra] = rb
    return true
  }
}

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

Union-Find or BFS?

Are these two connected? - Union-Find, especially asked repeatedly.
How many groups? - Union-Find.
Edges arrive over time - Union-Find. BFS would restart from scratch each time.
What is the path? - BFS or DFS. Union-Find cannot tell you.
Shortest path? - BFS. Union-Find has no notion of distance.

It is also the engine inside Kruskal's minimum spanning tree algorithm, which is the other place it shows up by name.

Both optimisations, and why each matters

Path compression flattens the tree during find, so repeated lookups get cheaper. Union by rank attaches the shorter tree under the taller one, so the tree never gets deep in the first place. With both, each operation is effectively constant time.

Union-Find with both optimisations

javascript

class UnionFind {
  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) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]   // halve the path
      x = this.parent[x]
    }
    return x
  }

  union(a, b) {
    const rootA = this.find(a)
    const rootB = this.find(b)
    if (rootA === rootB) return false   // already connected

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA
    } else {
      this.parent[rootB] = rootA
      this.rank[rootA]++
    }

    this.count--
    return true
  }

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

const demoUf = new UnionFind(4)
console.log(demoUf.union(0, 1))  // true — newly joined
console.log(demoUf.union(0, 1))  // false — already connected
console.log(demoUf.count)        // 3

union returning false for an existing connection is what makes cycle detection a one-liner: in Kruskal's algorithm, an edge that fails to union is an edge that would close a cycle, so you skip it.

When to reach for it

Connectivity questions with no need for the actual path - counting islands or provinces, detecting cycles in an undirected graph, building a minimum spanning tree. If you need the route between two nodes rather than just whether one exists, use BFS or DFS instead.

PreviousDijkstra's Algorithm NextDynamic Programming Explained