Are they already connected?

An office adds network cables one at a time. Some cables are wasted: they join two computers that could already reach each other through earlier cables.

Before plugging in a cable, ask union-find: do these two computers already have the same leader? If they do, the cable only adds a loop. It connects nothing new.

Same leader already? the cable is wasted.

4 computers, cables 0–1, 1–2, 0–2, 2–3

unnecessary: 0

Cable 0-1: different leaders. Merge: 0 now points to 1.

Move 1 of 4

Count it, don't merge it

For a wasted cable, add 1 to the count and move on: there's nothing to merge. Every other cable merges as usual.

Ask the question before merging, not after. Once you've merged, the two ends always share a leader, so everything would look wasted. For cables 0-1, 1-2, 0-2, 2-3, only 0-2 is wasted.

Check before merging: after merging, everything looks connected.

In code

parent = list(range(n))
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x
wasted = 0
for a, b in edges:
    ra, rb = find(a), find(b)
    if ra == rb:
        wasted += 1
    else:
        parent[ra] = rb
return wasted