Redundant Connection
You get a graph that started life as a tree with n nodes labeled 1 to n, and then exactly one extra edge was added (between two existing, distinct nodes, not duplicating an existing edge). Given the resulting list of n edges, find an edge that can be removed so the graph becomes a tree again. If several answers are possible, return the one that appears last in the input list.
Examples
- Input:
- edges = [[1,2],[1,3],[2,3]]
- Output:
- [2,3]
Nodes 1, 2, 3 form a triangle. Removing any one edge restores a tree, and [2,3] is the last of the three in the input.
- Input:
- edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
- Output:
- [1,4]
The cycle is 1-2-3-4-1. [1,4] is the cycle edge appearing latest in the list ([1,5] is not in the cycle, so removing it would disconnect node 5).
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.