Redundant Connection
Redundant Connection: A tree of n nodes had one extra edge added, creating exactly one cycle. Find the redundant edge that can be removed.
- n == edges.length
- 3 <= n <= 1000
- edges[i].length == 2
- 1 <= ai < bi <= edges.length
- ai != bi
- There are no repeated edges.
- The given graph is connected.
Intuition
Redundant connection takes a tree that had one extra edge added, creating exactly one cycle, and asks which edge to remove. When several edges could be removed, the answer is the one appearing last in the input.
The tempting plan is to find the cycle first — with a DFS — and then choose an edge from it. That works but requires locating the cycle, extracting its edges, and then deciding which one the problem wants.
Union-Find answers it in a single pass with no cycle-finding at all. Process the edges in the given order, and for each, ask whether its two endpoints are already connected:
- If two endpoints already share a root, this edge closes a cycle — and since edges are processed in order, it is the last such edge.
That directly satisfies the tie-break rule without any extra reasoning. The first edge to fail the connectivity test is the answer, so the loop can return immediately.
If the endpoints are in different components, the edge is a legitimate tree edge — union the two sets and continue.
Two optimisations make Union-Find behave. Path compression flattens the tree on each find, and union by rank or size keeps merges shallow. Without them the structure can degenerate into a linked list and each find becomes O(n); with them the amortised cost is effectively constant.
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
Before reading on: price up what the direct approach costs here, then ask whether you are really just merging groups and asking what connects. Aim for O(n * alpha(n)) time and O(n) space.
Process edges in the given order
The problem asks for the last removable edge, and processing in input order means the first edge that closes a cycle is exactly that one. No separate tie-break logic is needed.
Ask whether the endpoints are already connected
For each edge, compare the roots of its two vertices. Same root means both are already in one component, so this edge creates a cycle.
Return the first cycle-closing edge
When find(u) == find(v), return that edge immediately. Exactly one such edge exists by the problem's construction, so no further scanning is required.
Union and continue otherwise
Different roots mean the edge joins two separate components — a legitimate tree edge. Union them and move on, growing the forest one edge at a time.
Apply both Union-Find optimisations
Path compression flattens the tree on each find; union by rank keeps merges shallow. Without them the structure degenerates into a linked list and each operation costs O(n) instead of near-constant.
Cost of the single pass
Each of the n edges does two near-constant find operations, giving O(n · α(n)) time — effectively linear — with O(n) space for the parent array. Compare with DFS cycle-finding, which is the same order but needs more code.
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.