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

3

Your union() is currently doing count-- on redundant unions too, not only on real merges.

A union-find should only reduce the component count when two different roots become one. If find(a) and find(b) already match, those nodes are already connected, so that call must be a no-op. Right now the bug is that redundant unions are being counted like new merges.

The smallest fix is this:

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

  if (ra === rb) return;

  this.p[ra] = rb;
  this.count--;
}

Tiny version of the rule:

if (find(a) === find(b)) return;

With ra and rb checked before this.count--, the count stays honest:

  • this.find(a) and this.find(b) get the current roots of each component.
  • if (ra === rb) return; ensures only actual merges decrement count.

So union(0, 2) becomes a true no-op once 0 and 2 are already connected.

You can see it with the same case here:

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
console.log(d.find(0) === d.find(2)); // expected: true

If you later add union by rank/size, this same guard still stays.

BobaMilk

4

@BobaMilk’s union(0, 2) no-op point is right, and the other easy edge case is union(x, x) which should also leave count alone or you’ll burn one component on a self-loop.

Ellen