Asked at
Redundant Connection
MediumVerifiedUnion FindGraphDFS~25 min
You have an undirected graph that started as a tree over n nodes labeled 1..n, with exactly one extra edge added. The result has a single cycle.
Return the edge that can be removed so the graph becomes a tree again. If several edges qualify, return the one that appears last in edges.
The input arrives as a single number[][] of [u, v] edges.
Examples
in[[1,2],[1,3],[2,3]]
out[2, 3]
Removing [2,3] leaves a valid tree; it is the cycle-closing edge.
in[[1,2],[2,3],[3,4],[1,4],[1,5]]
out[1, 4]
[1,4] closes the cycle 1-2-3-4-1, so it is removed.
Constraints
- 3 ≤ n ≤ 1000
- edges.length == n
- edges[i] = [u, v] is an undirected edge, nodes labeled 1..n
- The graph is a tree plus exactly one extra edge.
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.