Redundant Connection
A tree with n nodes had one extra undirected edge added, creating exactly one cycle. Given the resulting edge list, return the edge that can be removed to restore a tree; if several qualify, return the one that appears last in the input.
- 3 ≤ n ≤ 1000
- edges.length = n
- No repeated edges
- Edges arrive in order and the last one closing a cycle is the answer
- An edge closes a cycle when both endpoints are already in the same set
- Incremental connectivity
When connectivity is built up incrementally by unions and queried repeatedly, disjoint sets with path compression and union by rank answer both in near-constant amortized time, without rebuilding anything. It is the right tool whenever DFS would have to be rerun after each new edge, and it is the engine of Kruskal's MST.
Process edges in input order with a disjoint-set structure. For each edge, find the roots of its endpoints; if they are already equal the edge connects two nodes that are already connected, so it closes the cycle — return it. Otherwise union the two sets. Because the tree plus one edge has exactly one cycle, the first edge found this way is also the last one that can be removed.
- For each edge, check with DFS whether its endpoints are already connected before adding it — O(n^2) in total.