A tree with n nodes, numbered from 1 to n, had one extra edge added between two of its nodes
that weren't already joined directly. You are given the n edges of the result, edges, where
each [a, b] (with a < b) joins nodes a and b. Edges have no direction.
Return an edge you can remove so that the remaining edges form a tree again: connected, with no
cycle. If several edges would work, return the one that comes last in edges.
Example 1
- Input
- edges = [[1, 4], [3, 4], [1, 3], [1, 2], [4, 5]]
- Output
- [1, 3]
[1, 3] is the last of them in the list.Example 2
- Input
- edges = [[2, 3], [1, 2], [3, 5], [4, 5], [1, 5]]
- Output
- [1, 5]
[1, 5] closes it last.Constraints
- 3 ≤
n≤ 1000 edgesholds exactlynedges, each[a, b]with 1 ≤a<b≤n, and no edge appears twice.- The edges connect all
nnodes.
Show the pattern
Union-find
Adding the edges one at a time, the edge to remove is the first one whose two ends are already connected. Union-find answers "already connected?" for each edge as it arrives.
See union-find in a visualiserShow the approach
Add the edges in order to a union-find structure over the nodes 1 to n. For each edge [a, b],
find the roots of a and b. If they are the same, a and b are already connected, so this
edge closes the cycle: return it. Otherwise union the two groups and go on.
Why this is the right edge: the edges whose removal leaves a tree are exactly the edges on the cycle. The cycle's two ends can only be connected once all of its other edges have been added, so the first edge found joining connected nodes is the cycle edge that comes last in the list.
Time: O(n log n), close to linear in practice · Space: O(n)