Redundant Connection
MediumP3Coding
A tree was built on n nodes labelled 1..n, and then one extra edge was added, so the graph now has exactly one cycle. edges lists the n undirected edges in the order they were added.
Return the edge that can be removed so the remaining graph is a tree. If several edges could be removed, return the one that appears last in edges.
Example 1
- Input
- edges = [[1,2],[1,3],[2,3]]
- Output
- [2,3]
Example 2
- Input
- edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
- Output
- [1,4]
- Why
- Edges 1-2, 2-3, 3-4 already connect 1 and 4.
Constraints
- 3 <= n <= 1000
- edges.length == n
- 1 <= a < b <= n or a, b given in either order, a != b
- No repeated edges, and the graph is connected.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 8. ⌘Enter runs, ⌘⇧Enter submits.