Redundant Connection

Problem

You start with a tree on n nodes labeled 1..n (a connected graph with no cycles) and then one extra edge is added between two nodes that were not already directly connected. You are handed the resulting n edges as a list edges, where edges[i] = [a, b] is an undirected edge, in some order.

Return an edge that can be deleted so that what remains is again a tree on all n nodes. If more than one edge would work, return the one that appears latest in edges.

• There are exactly as many edges as nodes, and at least three of each; a few thousand nodes at most.
• Endpoints are node labels in 1..n; no self-loops and no edge is listed twice.
• The input always consists of one tree plus one additional edge, so a valid answer exists.

Examples

• edges = [[4,5],[2,4],[1,2],[3,5],[1,3],[5,6]] → [1,3]. Nodes 1-2-4-5-3 form the only cycle; [5,6] hangs off it and is not removable. [1,3] is the last cycle edge in the input.
• edges = [[1,2],[1,3],[1,4],[2,4]] → [2,4]. The cycle is 1-2-4; [1,3] is a leaf edge, and [2,4] is the cycle edge listed last.
• edges = [[2,6],[1,6],[3,4],[3,6],[1,4],[5,2]] → [1,4]. Removing [1,6], [3,6], [3,4] or [1,4] all leave a tree; [1,4] comes latest.

Hints

1. A tree with n nodes has exactly n - 1 edges. What does adding one edge to a tree always create?
2. Process edges in input order. What is special about the moment you try to add an edge whose two endpoints are already reachable from each other?
3. Union-find: the first edge that joins two nodes already in the same component is the answer.