Redundant Connection
MediumGraphs
An undirected graph started out as a tree on n nodes labelled 1 to n. Then one extra edge was added between two different nodes that were not already directly connected, so the graph now has n edges and exactly one cycle.
You are given that graph as a list edges, where edges[i] = [a_i, b_i] (with a_i < b_i) is an undirected edge. Return an edge whose removal turns the graph back into a tree on all n nodes.
Any edge on the cycle would work, so to make the answer unique: return the one that appears last in edges. Return it exactly as it appears in the input.
Example 1
- Input:
- edges = [[1, 2], [2, 3], [3, 4], [2, 4], [4, 5]]
- Output:
- [2, 4]
- Explanation
- The cycle is
2 - 3 - 4 - 2, made of[2, 3],[3, 4]and[2, 4]. Of those,[2, 4]appears last.[4, 5]comes later in the list but is not on the cycle, so removing it would disconnect node 5.
Example 2
- Input:
- edges = [[3, 4], [1, 4], [1, 3], [2, 3]]
- Output:
- [1, 3]
- Explanation
- Nodes 1, 3 and 4 form a triangle.
[1, 3]is the last triangle edge in the list;[2, 3]only attaches node 2.
Example 3
- Input:
- edges = [[1, 5], [1, 2], [2, 3], [3, 4], [4, 5]]
- Output:
- [4, 5]
- Explanation
- All five edges form one big cycle, so removing any of them leaves a tree. The tie goes to the edge listed last,
[4, 5].
Constraints
n == edges.length- 3 ≤
n≤ 1000 edges[i].length == 2and 1 ≤a_i<b_i≤n- There are no repeated edges, and the graph is connected