Union-Find (Disjoint Sets)

Union-Find (Disjoint Sets) — DSA Tutorial - HTML5ANDCSS3

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 }
}

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

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
}

What it does

Counting groups

Detecting a cycle

Union-Find or BFS?