Why does this union-find count too many connected components after repeated unions?

programming web dev
1

I’m implementing union-find for grouping related IDs, but my component count is too high after unions that connect nodes already in the same set. I expected the count to decrease only when two roots differ. What is wrong with this implementation?

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

For example, union(0,1), union(1,2), union(0,2) leaves count too small.

MechaPrime

2

Your union always decrements count, so the duplicate merge union(0,2) still subtracts one even though find(0) === find(2) by then.

Quelly