Redundant Connection
A tree of n nodes had one extra edge added, creating exactly one cycle. Find the redundant edge that can be removed.
Open on LeetCode ↗Intuition
The trap is trying to find the cycle first and then picking an edge out of it. Union-Find answers this in a single pass: process the edges in the given order, and the first edge whose two endpoints already share a root is exactly the edge that closes a cycle -- everything before it built a valid forest. Because a valid tree on n nodes has exactly n-1 edges, and this input has n, there is exactly one such moment, and returning immediately there gives the LAST such edge in input order, which is precisely what the problem asks for.
Union-find processing edges in order. The first edge whose endpoints already share a root closes a cycle, and since the input has exactly one extra edge, that edge is the answer. Processing in order is what satisfies the "return the last such edge" requirement.
Approach
Union-Find, one pass over edges
Maintain a parent array. For each edge [u, v] in order, find the roots of u and v.
Same root means redundant
If find(u) == find(v), the two nodes were already connected before this edge -- adding it creates a cycle. Return this edge immediately; no need to search for the cycle explicitly.
Different roots means union and continue
Otherwise union the two sets (attach one root under the other) and move to the next edge -- this edge is a legitimate tree edge.
Solution & live demo
Common pitfalls
Continuing after finding a cycle
if ru == rv:
answer = [u, v]if ru == rv:
return [u, v]With exactly one redundant edge, the first cycle detected is the only one — and once it's added the structure is no longer a forest, so later detections would be spurious. Returning immediately is both correct and necessary.
Uniting before checking
parent[ru] = rv if ru == rv: return [u, v]
if ru == rv: return [u, v] parent[ru] = rv
Merging first makes the roots equal by construction, so the test can never fire. The cycle check must read the state from before the union.
Sizing the parent array to n
parent = list(range(n))
parent = list(range(n + 1))
Vertices are labelled 1 through n, so index n must exist. A zero-based array of length n throws on the highest-numbered vertex.
Edge cases
Union-Find catches it the instant both endpoints share a root -- no lookahead needed.
Problem guarantees exactly one extra edge, so only one edge ever finds matching roots.
find(a) == find(a) trivially -- would be reported as redundant immediately.
Processing in input order and returning at the first same-root hit naturally gives the last edge in the original list that closes the cycle.