Why does this union-find component counter overcount after redundant unions?

programming web dev
1

I’m tracking the number of connected components with a basic union-find, but the count becomes too high after processing edges that connect nodes already in the same set. I expected redundant unions to leave the component count unchanged. What is the bug in this implementation?

class DSU {
  constructor(n) { this.p = Array.from({ length: n }, (_, i) => i); this.count = n; }
  find(x) { return this.p[x] === x ? x : this.find(this.p[x]); }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    this.p[ra] = rb;
    this.count--;
  }
}
const d = new DSU(4);
d.union(0, 1); d.union(1, 2); d.union(0, 2);

WaffleFries

2

Your union() is currently doing count-- on every call, not only when two different components actually merge.

A union-find should only reduce the component count when the two nodes have different roots. After union(0, 1) and union(1, 2), both 0 and 2 already belong to the same set, so union(0, 2) should be a no-op. The bug is that you always re-parent and decrement, even for redundant unions.

Tiny version of the issue:


js
if (find(a) === find(b)) {
  // already connected, so count must not change
}

Minimal Fix


js
union(a, b) {
  const ra = this.find(a);
  const rb = this.find(b);

  if (ra === rb) return;

  this.p[ra] = rb;
  this.count--;
}
  • find() gets the current root of each node.
  • ra === rb ensures only real merges reduce count.
  • This prevents redundant unions from overcounting the number of merges.

Sanity Check


js
class DSU {
  constructor(n) {
    this.p = Array.from({ length: n }, (_, i) => i);
    this.count = n;
  }

  find(x) {
    return this.p[x] === x ? x : this.find(this.p[x]);
  }

  union(a, b) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return;
    this.p[ra] = rb;
    this.count--;
  }
}

const d = new DSU(4);
d.union(0, 1);
d.union(1, 2);
d.union(0, 2);

console.log(d.count); // expected: 2

Short insight: in DSU, “same root” means “do nothing.”

Quelly