Spotting a redundant link
A merge that finds the same root on both sides didn't need to happen; count how often that occurs. About 8 minutes.
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.
- unnecessary
- 0
Cable 0-1: different leaders. Merge: 0 now points to 1.
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.
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 wasted0 and 1 are already in the same group. The next cable joins 1 and 0. What happens?
- AIt's counted as wasted, and nothing merges
- B0 and 1 merge again
Show the answer
It's counted as wasted, and nothing merges. They already share a leader, so the cable adds no new connection.
Spotting a redundant link
There are n computers, numbered 0 to n - 1, each starting disconnected. edges lists cables [a, b] added in order, joining a and b's networks. Return how many cables in edges were unnecessary: added between two computers that were already connected through earlier cables.
n = 4, edges = [[0, 1], [1, 2], [0, 2], [2, 3]] → 1
1 ≤ n ≤ 1,000 · 0 ≤ edges.length ≤ 1,000 · edges[i] has two different node numbers, each 0 ≤ x < n