Graph BFS / DFS
LC #684Medium
Redundant Connection
Graph BFS / DFS
AmazonGoogleLinkedInProblem
In a tree with n nodes and n edges (one extra edge creates a cycle), find the redundant edge that can be removed to restore the tree.
graphunion-find
Constraints
- ›n == edges.length
- ›3 ≤ n ≤ 1000
- ›edges[i].length == 2
- ›1 ≤ ai < bi ≤ n
- ›No repeated edges
Example
Input
edges = [[1,2],[1,3],[2,3]]Output
[2, 3]Why
[2,3] is the last edge that creates a cycle. Removing it leaves a valid tree.