Find the Redundant Dependency Edge
A build system's module graph should be a tree (one root, no cycles). Someone added one extra dependency edge, creating a cycle. Identify the edge that, if removed, restores the tree — report the last such edge in input order.
Problem
A tree with n nodes (labeled 1..n) had one extra edge added, producing a graph with n nodes and n edges that contains exactly one cycle. Given edges in the order they were added, return the edge that can be removed so the result is a tree. If multiple answers exist, return the edge that occurs last in the input.
Input
An array edges where edges[i] = [u, v]; n edges, nodes labeled 1..n.
Output
An array [u, v]: the redundant edge to remove.
Constraints
- 3 <= n <= 1000
- edges.length == n
- 1 <= u < v <= n, no repeated edges.
Examples
Example 1
Input
edges = [[1,2],[1,3],[2,3]]
Output
[2,3]
Adding [2,3] closes the cycle 1-2-3-1.
Example 2
Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output
[1,4]
[1,4] closes a cycle; it is the last cycle-forming edge.