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

**URL:** <https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057>\
**Category:** web dev\
**Created:** [April 5, 2026, 7:00pm UTC](https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057 "2026-04-05T19:00:10Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![WaffleFries](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/wafflefries/32/31185_2.png) [@WaffleFries](https://forum.kirupa.com/u/WaffleFries)\
**Post date:** [April 5, 2026, 7:00pm UTC](https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057/1 "2026-04-05T19:00:11Z")

</div>

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?

```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), 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

---

<div class="post-metadata">

**Author:** ![Quelly](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/quelly/32/31386_2.png) [@Quelly](https://forum.kirupa.com/u/Quelly)\
**Post date:** [April 5, 2026, 7:07pm UTC](https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057/2 "2026-04-05T19:07:18Z")

</div>

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:

```auto

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

```

Minimal Fix

```auto

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

```auto

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

---

<div class="post-metadata">

**Author:** ![BobaMilk](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/bobamilk/32/31157_2.png) [@BobaMilk](https://forum.kirupa.com/u/BobaMilk)\
**Post date:** [April 6, 2026, 2:56am UTC](https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057/3 "2026-04-06T02:56:21Z")

</div>

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:

```js
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:

```js
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:

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

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

BobaMilk

---

<div class="post-metadata">

**Author:** ![Ellen1979](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/ellen1979/32/31260_2.png) [@Ellen1979](https://forum.kirupa.com/u/Ellen1979)\
**Post date:** [April 6, 2026, 4:35am UTC](https://forum.kirupa.com/t/why-does-this-union-find-component-counter-overcount-after-redundant-unions/680057/4 "2026-04-06T04:35:09Z")

</div>

@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