Redundant Connection and Cycle Detection
Detect the edge that creates a cycle in an undirected graph by applying union on each edge and checking if two nodes are already connected.
What Is a Redundant Connection?
The Redundant Connection problem (LeetCode 684) gives you a tree of n nodes and one extra edge, forming exactly one cycle. Your task is to find the edge that, when removed, restores the tree. If multiple answers exist, return the last one in the input list.
A tree with n nodes has exactly n-1 edges and is connected with no cycles. Adding one more edge creates exactly one cycle. The added (redundant) edge connects two nodes that were already in the same component — a classic DSU cycle-detection scenario.
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')Cycle Detection with DSU
DSU detects cycles naturally: before adding an edge (u, v), check if find(u) == find(v). If they share a root, they are already connected — adding this edge creates a cycle. This is the redundant edge.
This approach works for undirected graphs. For each edge, we either successfully union the two components (no cycle yet) or detect that both endpoints are already in the same component (cycle found). The time complexity is O(n × alpha(n)), nearly O(n).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]All lessons in this course
- DSU with Path Compression
- Union by Rank and the Inverse Ackermann Bound
- Redundant Connection and Cycle Detection
- Accounts Merge and Connected Components