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.
Redundant Connection and Cycle Detection is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]Tracing Through the Algorithm
Let us trace [[1,2],[1,3],[2,3]] step by step. Initially, each node is its own component: {1}, {2}, {3}.
- Edge [1,2]: find(1)=1, find(2)=2, different — union them. Components: {1,2}, {3}
- Edge [1,3]: find(1)=root, find(3)=3, different — union them. Components: {1,2,3}
- Edge [2,3]: find(2)=root, find(3)=root — same root! Cycle detected. Return [2,3].
The algorithm processes edges in order and returns the first edge that completes a cycle. Because the problem guarantees only one extra edge, this is always the correct redundant edge.
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)Cycle Detection in Undirected Graphs with DFS
An alternative to DSU for cycle detection in undirected graphs is DFS with parent tracking. During DFS, if we reach a node that is already visited and is not the direct parent of the current node, we have found a back edge — indicating a cycle.
However, the DFS approach requires O(V + E) time and returns whether a cycle exists but not easily which specific edge is redundant. DSU is preferred for problems that ask you to identify the specific redundant edge because you naturally find it when the union fails.
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # FalseCycle Detection in Directed Graphs
For directed graphs, DSU cycle detection does not work directly because edges have direction. Instead, use DFS with three-color marking: white (unvisited), grey (in the current DFS path), black (fully processed). A back edge to a grey node indicates a cycle.
In an undirected graph, any back edge means a cycle. In a directed graph, a cross edge to a black node is not a cycle — only back edges to grey nodes are. This distinction is critical and is tested in course-schedule problems.
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # FalseRedundant Connection II: Directed Graph Variant
LeetCode 685 extends the problem to directed graphs where each node has exactly one parent (forming a rooted tree with one extra edge). Two cases arise: either a node has two parents (in-degree 2), or there is a cycle with no node having two parents.
The solution checks for nodes with in-degree 2 first. If found, one of its two incoming edges must be the answer. Then DSU cycle detection determines which of the two candidate edges to remove. This two-phase approach handles all cases correctly.
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]Graph Validity After Edge Removal
After identifying the redundant edge, we can verify the result by checking that removing it leaves a valid tree: exactly n-1 edges, all nodes connected, no cycles. For the purposes of the interview problem, the DSU naturally guarantees this — if we return the edge that failed the union, removing it leaves us with exactly the n-1 edges that were successfully unioned, which form a spanning tree.
This guarantee is why DSU is so clean for this problem: successful unions build the tree incrementally, and the failed union identifies the one edge that does not belong.
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removalTime and Space Complexity Analysis
The DSU-based redundant connection solution processes each of the n edges exactly once, and each union/find operation costs O(alpha(n)) amortised. Total time: O(n × alpha(n)), effectively O(n).
Space complexity is O(n) for the parent and rank arrays. This is optimal — you must at minimum read all n edges and store some state per node. Compare this to a naive approach that runs DFS after each edge insertion: O(n²) time and O(n + E) space.
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')Edge Case: Self-Loop
A self-loop edge [u, u] immediately creates a cycle since both endpoints are the same node. In DSU, find(u) == find(u) is always true, so the union fails immediately and [u, u] is returned as the redundant edge.
Most problem constraints guarantee no self-loops, but robust code should handle this. The DSU implementation naturally handles it without any special case — the cycle check if find(u) == find(v) catches it before any union is attempted. Always verify with edge-case inputs like single-node loops and minimum-size inputs.
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]Generalising Cycle Detection Across Algorithms
Multiple algorithms detect cycles, each suited to different scenarios:
- DSU: undirected graphs, online edge arrival, O(alpha(n)) per edge — best for counting or finding the redundant edge
- DFS with parent tracking: undirected graphs, all edges known upfront, O(V+E) — best when you need the cycle path
- DFS three-color: directed graphs, detecting back edges, O(V+E) — best for course-schedule and topological sort
- Topological sort (Kahn's): directed graphs, detects cycle via leftover non-zero in-degree nodes — best when you also need ordering
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')Full Solution with Edge Cases
Here is a production-quality solution to Redundant Connection that handles all edge cases: 1-indexed nodes, exactly one redundant edge, and the guarantee that removing it leaves a valid tree. It uses the optimal DSU with path halving and union by rank.
After submitting, try the follow-up: what if the graph could have multiple redundant edges? You would need to track all edges that complete a cycle and return the last one in the input — the same greedy strategy still works because DSU processes edges in order.
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
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]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a redundant connection is an edge that connects two already-connected nodes in an undirected graph, DSU detects this by checking find(u) == find(v) before union and returning that edge, and directed graphs require three-color DFS or Kahn's algorithm instead of DSU for cycle detection. Next up we apply DSU to the accounts-merge problem, where emails are the nodes and shared emails between accounts trigger unions.
Frequently asked questions
Is the “Redundant Connection and Cycle Detection” lesson free?
Yes — the full text of “Redundant Connection and Cycle Detection” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Redundant Connection and Cycle Detection” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
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