Redundant Connection
Medium · union find
A group of n towns, numbered 1 to n, was joined by exactly n - 1 roads so that you could travel between any two towns in exactly one way. Then one extra road was built between two towns that were already connected. You are given all n roads as a list edges, where each entry [a, b] is a two-way road between town a and town b.
The extra road created a loop, so one road is now unnecessary. Return a road that you can close so that the towns are again connected by exactly one route between any two of them.
Several roads may fit (any road on the loop works). In that case return the one that appears last in edges. Return it exactly as it is written in the list, with the same order of the two towns.
The same pair of towns may be listed twice. In that case the second copy is the one that appears later, so it is the one to return.
Examples
Example 1
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Towns 1, 2 and 3 form a loop, and any of its three roads could be closed. The last of them in the list is [2, 3].
Example 2
Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
The loop is 1, 2, 3, 4. Town 5 hangs off it with a single road, so [1, 5] is not part of the loop. The last loop road in the list is [1, 4].
Example 3
Input: edges = [[1, 2], [1, 2]]
Output: [1, 2]
The same road was built twice. Either copy could be closed, and the second one is later in the list.
Constraints
- 2 <= len(edges) <= 1000
- The towns are numbered 1 to len(edges), and every road joins two different towns.
- The roads are exactly a connected network plus one extra road, so there is always an answer.