752. The Extra Cable
A village wired its n houses, numbered 1 to n, with n - 1 cables so that power reaches every house. Later an electrician laid one additional cable by mistake. The list edges therefore has n entries; each entry [a, b] is a cable joining houses a and b in both directions, and no pair of houses is joined twice. Power still reaches every house, but the network now contains exactly one loop.
Remove exactly one cable so that the remaining cables again connect all houses without any loop. Return the removed cable written exactly as it appears in edges. If several cables would work, return the one that appears last in edges.
Example 1
- Input:
- edges = [[1,2],[1,3],[2,4],[3,4]]
- Output:
- [3,4]
- Explanation:
The four cables form the loop 1-2-4-3-1. Any of them could go, and the last one listed,
[3, 4], is returned.
Example 2
- Input:
- edges = [[4,1],[2,3],[1,2],[3,1]]
- Output:
- [3,1]
- Explanation:
Only the cables
[2, 3],[1, 2]and[3, 1]lie on the loop; house 4 hangs off it. The last of them in the list is[3, 1].
Example 3
- Input:
- edges = [[5,2],[2,3],[3,4],[4,5],[1,5]]
- Output:
- [4,5]
- Explanation:
The loop is 5-2-3-4-5; the cable
[1, 5]is a dangling link to house 1 and must stay. The last loop cable is[4, 5].
Constraints
- 3 ≤ n = edges.length ≤ 105
- edges[i] = [a, b] with 1 ≤ a, b ≤ n and a ≠ b
- No pair of houses appears twice; the network is connected and contains exactly one loop
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n * alpha(n))
- Space
- O(n)