Which cable can be removed?
The same redundancy check as before, but this time report the actual edge instead of a count. About 9 minutes.
Report the wasted cable
A building's network has exactly one cable too many: n computers, n cables, when n − 1 would have connected them all. Somewhere, one cable joins two computers that were already connected.
It's the same check as counting wasted cables. But instead of counting, stop and report the cable the moment you find one whose two ends already share a leader.
Cable 0-1: different leaders. Merge.
Why there's always exactly one
Connecting n computers into one network needs exactly n − 1 cables if none are wasted. With n cables and everything connected, exactly one cable must be surplus. Adding the cables in order, it's the first one that finds its two ends already joined.
For cables 0-1, 1-2 and 2-0: by the time 2-0 arrives, all three are connected. That's the one.
if ra == rb:
return edge # closes a loopCables 0-1, 1-2 and 2-0 are added in that order. Which one is surplus?
- A2-0
- B0-1
Show the answer
2-0. By the time it arrives, 0, 1 and 2 are already connected by the first two cables.
Which cable can be removed?
There are n computers, numbered 0 to n - 1. edges lists n cables [a, b], added in order, and together they connect every computer with exactly one cable more than a tree needs. Return the one cable that connects two computers already joined by earlier cables.
n = 3, edges = [[0, 1], [1, 2], [2, 0]] → [2, 0]
3 ≤ n ≤ 100,000 · edges.length == n · every pair has two different node numbers, each 0 ≤ x < n · exactly one edge is redundant