Graph Exploration Target: 15s
Three colors: white (unvisited), gray (in current path), black (finished). Gray → gray = cycle in directed graph.
def hasCycle(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white, 1=gray (in stack), 2=black (done)
color = [0] * n
def dfs(u):
color[u] = 1 # gray: entering
for v in graph[u]:
if color[v] == 1: return True # back edge → cycle
if color[v] == 0 and dfs(v): return True
color[u] = 2 # black: done
return False
return any(color[i] == 0 and dfs(i) for i in range(n))Type it from memory. Go.