Redundant Connection
Find the edge that creates a cycle — where union-find beats a traversal, because the answer is decided the moment an edge arrives
Problem Statement
You start with a tree of n nodes, then one extra edge is added, creating exactly one cycle. Return that edge. If several answers exist, return the one appearing last in the input.
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
1
/ \
2 - 3 the edge 2-3 closes the cycle
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]Intuition
The DFS approach: for each edge, check whether its two nodes are already connected — if so, this edge closes a cycle. But "are these connected?" means a fresh traversal every time, so the whole thing is O(n²).
The insight
An edge creates a cycle exactly when both endpoints are already in the same group.
If they are in different groups, the edge is doing useful work — joining two separate pieces. If they are already joined, there is already a path between them, and adding a second one closes a loop.
That is precisely the question union-find answers in near-constant time. Process the edges in order, and the first one whose endpoints already share a root is the answer.
This is where union-find earns its place over DFS. The edges arrive one at a time, and each must be judged against everything seen so far. Union-find absorbs each edge and keeps answering instantly; DFS would re-walk the graph on every edge.
Why the first failure is also the LAST valid answer
The problem asks for the last edge in the input that could be removed.
Every edge before the cycle-closing one was a genuine merge — remove any of those and the graph falls apart. Only the edge that found its endpoints already connected is redundant.
Since exactly one extra edge was added, there is exactly one such edge, and returning it on first detection satisfies "last in the input" automatically.
Approach
For each edge, look up both roots
find(a) and find(b).
Same root → this is the answer
The two nodes were already connected. This edge is redundant. Return it.
Solution
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
"""Return the edge that creates a cycle.
Nodes are labelled 1..n, so the arrays are sized n + 1.
"""
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for a, b in edges:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return [a, b] # already connected → cycle
if rank[root_a] < rank[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
if rank[root_a] == rank[root_b]:
rank[root_a] += 1
return [] # unreachable per the problemlist(range(n + 1)) sizes the array for 1-based labels. Using n would put an index error on the highest-numbered node.
Complexity Analysis
Time Complexity
O(n·α(n))
Space Complexity
O(n)
Time — one pass over the edges, with two near-constant find calls each. α(n) is the inverse Ackermann function, under 5 for any realistic input.
Compare the DFS approach at O(n²): a traversal per edge to test connectivity.
Space — the parent and rank arrays.
Edge Cases
Related Problems
- Number of Provinces — union-find introduced, with both optimisations explained
- Course Schedule — cycle detection on a directed graph, where union-find does not apply
- Graphs — why cycles are the defining hazard