Find the Cable That Closes the Loop
Implement extraLink
A company connected n computers with exactly n cables, one more than a tree needs, so the network has exactly one loop. You are given the cables in the order they were installed. Return the cable to remove so that all computers stay connected; if several cables work, return the one that appears last in the list.
Adding the cables one by one to a union-find structure reveals the answer: the cable whose ends are already connected when it arrives is the one that closes the loop.
Example 1:
Input: links = [[0,1],[2,4],[1,2],[3,4],[4,5],[2,3]]
Output: [2,3]
Example 2:
Input: links = [[0,1],[1,2],[2,0]]
Output: [2,0]
Example 3:
Input: links = [[1,0],[2,1],[0,2]]
Output: [0,2]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
3 ≤ n ≤ 9 computers numbered 0 … n-1; links is a list of exactly n cables [u, v] (the graph as an edge list, in the order the cables were installed; the same graph is also the adjacency list built from these pairs) - ●
The cables connect all n computers; a network of n computers connected by n − 1 cables would be a tree, so exactly one loop exists (no cable repeats and there are no cables from a computer to itself) - ●
Removing any cable of the loop leaves a network that is still connected - ●
Return the cable [u, v] to remove: if several cables can be removed, the one that appears LAST in links (returned in the same orientation as it appears)
links =
[[0,1], [2,4], [1,2], [3,4], [4,5], [2,3]]