Given a directed graph as an adjacency list, return true if it contains a
cycle (a path that returns to a node already on the current path).
hasCycle(graph)
Input format: a,b pairs meaning directed edges a → b.
a,b b,c c,a // → true (a → b → c → a)
a,b b,c // → false
a,b b,c c,d d,b // → true (b → c → d → b)
For undirected graphs, one visited set was enough, since every edge is bidirectional — revisiting a seen neighbour never reveals new information. Directed graphs break this. Picture a diamond: a points to both b and c, and both point to d. Here d gets visited twice — via a→b→d and a→c→d — but that's not a cycle, just two paths converging. A plain "have I seen this node ever" check would wrongly flag this. You need to ask: have I seen this node earlier on the current path?
A cycle exists when, following a chain of edges, you arrive back at an ancestor of the current node in that same chain — not just any node visited before in an unrelated branch. That needs three states, not two:
When the DFS enters a node, mark it grey. Look at each outgoing edge: a grey neighbour means you've looped back to an active ancestor — a genuine cycle. A white neighbour, recurse. A black neighbour is already fully explored elsewhere and safe to skip. Only after exploring all of a node's neighbours do you mark it black.
Since grey specifically marks "currently an ancestor on the active path," any edge landing on a grey node is a back-edge — the definition of a cycle. And since you restart DFS from every remaining white node, disconnected pieces of the graph each get checked independently.
def has_cycle(graph):
WHITE, GREY, BLACK = 0, 1, 2
state = {}
def dfs(node):
state[node] = GREY
for nxt in graph.get(node, []):
if state.get(nxt, WHITE) == GREY:
return True
if state.get(nxt, WHITE) == WHITE and dfs(nxt):
return True
state[node] = BLACK
return False
for node in graph:
if state.get(node, WHITE) == WHITE and dfs(node):
return True
return False
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.