I thought we need just 1 visited list but we need another visited list for the current DFS path. This is cuz lets say we have
0->1->2->0. In the current DFS path, when we go from 2 to 0 and we see that we have visited 0 before. If we only have 1 visited list, we dk if this 0 has been visited before this current DFS path or whehter this 0 has been visited in this particular DFS path. So we need another visited list.
V.impt. We need to backtrack and undo all the changes for the current DFS path.
And the 2nd if statement. If we have visited this node before, this means we have explored this fully and there has been no cycle found (False). So recontinuing to this node will still result in no cycle. So we return false.
from collections import defaultdict
def solution(size, edges):
graph = defaultdict(list)
visited = [False] * size
dfs_checker = [False] * size
# Build graph
for i in range(0, len(edges), 2):
start, end = edges[i], edges[i+1]
graph[start].append(end)
def check_cycle(node):
if dfs_checker[node]: # Early return if node is in current DFS path
return True
if visited[node]: # If node has been fully explored before, skip it
return False
# Mark this node as visited and as part of the current DFS path
visited[node] = True
dfs_checker[node] = True
for neighbor in graph[node]:
if check_cycle(neighbor): # Recurse on neighbors
return True
dfs_checker[node] = False # Backtrack
return False
for node in range(size):
if not visited[node]:
if check_cycle(node):
return True
return False
# Test case
val = solution(4, [0, 1, 1, 2, 2, 3, 3, 1]) # Cycle exists (1 → 2 → 3 → 1)
print(val) # True
diff between topological sort
Method Analogy
DFS Cycle Detection You’re checking if a loop exists in a pipeline. You don’t care how long it is or where it goes. Just: “Is there a loop?” ✅/❌
Topological Sort You’re trying to list steps in order. If you find a step that depends on itself indirectly, you realise: “Ah, this can’t be ordered — there’s a cycle!”
