You get an array edges with the n edges of an undirected graph. Each edges[i] = [ai, bi] joins nodes ai and bi. The nodes are numbered 1 to n.
The graph started as a tree of n nodes. Then someone added one more edge between two nodes that weren't directly joined yet.
Return an edge you can remove to leave a tree on all n nodes. If more than one edge works, return the one that comes last in edges.
A tree is connected and has no cycle. Connected means a chain of edges leads from any node to any other. So in a tree, there is exactly one route between any two nodes.
Example 1:
Input: edges = [[1, 4], [3, 4], [1, 3], [2, 3]]
Output: [1, 3]
Explanation: The cycle is 1 - 4 - 3 - 1:
1 - 4
\ /
3 - 2
Removing any of its three edges leaves a tree.
Of the three, [1, 3] comes last.
[2, 3] comes later, but it is not on the cycle.
Without it, node 2 would be cut off.
Example 2:
Input: edges = [[2, 3], [1, 4], [1, 2], [3, 4]]
Output: [3, 4]
Explanation: All four edges form the cycle 1 - 2 - 3 - 4 - 1:
1 - 2
| |
4 - 3
Removing any of them leaves a tree.
[3, 4] comes last.
Constraints:
- 3 to 1,000 nodes.
- Exactly as many edges as nodes.
- In every edge, the smaller label comes first (
1 ≤ ai < bi ≤ n). - No edge is listed twice.
- The graph is connected.
Note:
Your algorithm should run in O(n·α(n)) time, nearly O(n), and use O(n) extra space.
Trying each edge from the last one back, removing it and checking with a DFS whether the rest is still connected, costs O(n2). The tutorial adds the edges one by one, in the order they are given, with union-find, as in Graph Valid Tree: an edge whose two nodes are already in the same group closes a cycle. The graph has exactly one cycle, and removing any of its edges leaves a tree, while removing an edge that is not on it cuts the tree in two. The cycle closes when the last of its edges comes, because all its other edges came before, so the first edge that closes a cycle is the answer. With path halving and union by size, each step costs O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any n a computer can hold.
Free plan: 30 tutor messages. PRO is unlimited.
