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.

edges = [[1,2],[1,3],[2,3]]           →  [2,3]
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]  →  [1,4]
edges = [[1,2],[2,3],[3,1]]           →  [3,1]

Solution

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 [[1,2],[1,3],[2,3]]: union(1,2) and union(1,3) both merge, linking 2 and 3 under root 1. union(2,3) finds find(2) == find(3) == 1, returns False, and we return [2,3].

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.