Redundant Connection

Problem

You are given n nodes labeled 1 to n and a list of edges forming a tree with one extra edge added. The extra edge creates exactly one cycle. Return the redundant edge - the edge that can be removed to restore the tree.

Example 1:

Input: edges = [[2,3],[1,3],[1,2]]
Output: [1,2]
Explanation: nodes 1 and 2 are already connected through node 3, so adding edge [1,2] closes the triangle.

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]

Example 3:

Input: edges = [[1,3],[3,2],[2,1]]
Output: [2,1]
Explanation: the third edge connects the already-connected pair 2 and 1.

Constraints:

• n == edges.length
• 3 <= n <= 500
• edges[i].length == 2
• 1 <= a, b <= n
• a != b
• There are no repeated edges and no self-loops in the given graph.
• The graph is connected and every node has exactly one parent except the root, with exactly one added edge.

Solution Breakdown

Approach - Union-Find that returns the first edge whose endpoints already share a root.

The input is a tree (a connected, acyclic graph on n nodes uses n - 1 edges) with one extra edge, so len(edges) equals the number of nodes. Nodes are labeled 1 to n, so we size parent and rank to n + 1 and let index i map directly to node i - no off-by-one bookkeeping. We then process edges strictly in input order. For each [a, b], union finds both roots: if they differ it links the trees (by rank) and returns True; if they already match, the two nodes are in the same component, so this edge closes a cycle and union returns False. The first edge that draws False is the redundant one, and we return it immediately.

Processing in order matters - the problem wants the last edge in the input that completes the cycle, which is exactly the first union failure when you walk forward. Trace [[2,3],[1,3],[1,2]]: union(2,3) and union(1,3) both merge, linking 1 and 2 under root 3. union(1,2) finds find(1) == find(2) == 3, returns False, and we return [1,2].

Edge cases - The guaranteed single extra edge means the loop always returns inside; the trailing return [] is a formality. Self-consistent 1-indexing avoids touching index 0.

Complexity - O(n * alpha(n)) time - n edges, each one near-constant union/find. O(n) space for the size-n+1 arrays.