Redundant connection
A network started out as a tree: n computers labeled 1 to n, joined by n - 1 two-way cables, so that every computer could reach every other one by exactly one route. Then someone added one more cable between two computers that were not joined directly. Now the network has a loop: a route that leaves a computer and comes back to it without using any cable twice.
You get all n cables in edges, each as [a, b] with a < b. Remove one cable so that the network is a tree again: every computer still reaches every other one, and there is no loop. More than one cable always works. Return the one that appears latest in edges, as the list [a, b].
edges = [[1, 2], [2, 3], [3, 4], [2, 4]]Output[2, 4]The cables [2, 3], [3, 4] and [2, 4] make the loop 2, 3, 4. Removing any one of them leaves a tree, and [2, 4] is listed last.
edges = [[1, 2], [3, 4], [2, 3], [1, 4]]Output[1, 4]All four cables make one loop, 1, 2, 3, 4, so any of them works, and [1, 4] is listed last. Both ends of [2, 3] appeared earlier, but in separate groups, so [2, 3] does not close the loop.
edges = [[1, 3], [3, 4], [1, 4], [2, 4], [2, 5]]Output[1, 4]The loop is 1, 3, 4. Removing [2, 4] or [2, 5] would cut computers off, so they do not count even though they come later.
3 ≤ n ≤ 105, and len(edges) == n
Every cable is [a, b] with 1 ≤ a < b ≤ n.
No cable is listed twice, and the cables connect all n computers.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.