Description
Given a graph that started as a tree with n nodes and one additional edge added, return an edge that can be removed so the graph becomes a tree.
Examples
Input:
edges = [[1,2],[1,3],[2,3]]Output:
[2,3]Explanation:
Removing [2,3] makes it a valid tree.
Input:
edges = [[1,2],[2,3],[3,4],[4,1]]Output:
[4,1]Explanation:
The edges form a cycle: 1-2-3-4-1. Since processing edges in order and the last edge [4,1] completes the cycle by connecting node 4 back to node 1 (which are already connected through the path 4-3-2-1), removing [4,1] breaks the cycle and creates a valid tree.
Input:
edges = [[2,3],[1,2],[1,3],[4,1],[5,4]]Output:
[1,3]Explanation:
After processing [2,3] and [1,2], there are a path 3-2-1. When encountering [1,3], it creates a cycle because nodes 1 and 3 are already connected through the path 1-2-3. Removing [1,3] eliminates the redundant connection while keeping all nodes connected in a tree structure.
Constraints
- •
n == edges.length - •
3 ≤ n ≤ 1000 - •
1 ≤ ai < bi ≤ n