457. Redundant Connection
A network started out as a tree: n nodes labeled 1 to n, joined by exactly n − 1 undirected edges and containing no cycles. Someone then added one extra edge between two distinct nodes that were not already directly connected.
You receive the resulting graph as an array edges of length n, where edges[i] = [u, v] is an undirected edge between nodes u and v.
Return an edge whose removal turns the graph back into a tree on all n nodes. If several edges qualify, return the one that appears last in the input — and report its endpoints in the same order as that input entry.
Example 1:
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: The three edges form the cycle 1–2–3–1. Any one of them could be dropped, so the tie-break picks [2, 3], the latest in the list.
Example 2:
Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Explanation: The cycle is 1–2–3–4–1, made of the edges [1,2], [2,3], [3,4] and [1,4]. Of those, [1,4] comes last in the input; [1,5] hangs off the cycle and is not removable.
Constraints:
- 3 ≤ n ≤ 1000
- edges.length == n
- 1 ≤ u, v ≤ n and u ≠ v
- There are no repeated edges, and the input is always a tree plus exactly one extra edge
Hints:
The extra edge creates exactly one cycle, and removing any edge of that cycle restores a tree. A direct plan: walk the edge list from the back, and for each edge test whether deleting it leaves all n nodes connected by the remaining n − 1 edges. That is n breadth-first searches — O(n²), correct, and a fine baseline.
Union-Find collapses this to one pass. Keep each node in a set; for every edge in input order, find the two endpoints' set representatives. If they differ, merge the sets. The first edge whose endpoints already share a representative closes the cycle — and because every other cycle edge was processed before it, it is exactly the removable edge that appears last in the input.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: edges = [[1, 2], [1, 3], [2, 3]]
Expected output: [2, 3]