"Does this graph have a cycle?" shows up in course schedule, deadlock detection, and dependency questions. There are three standard approaches, and the right one depends on whether the graph is directed.
Mark each node as unvisited (0), in the current path (1), or finished (2). If you reach a node marked 1, you have found a back edge, which means there is a cycle.
def has_cycle_directed(n, edges):
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
color = [0] * n
def dfs(u):
color[u] = 1
for v in g[u]:
if color[v] == 1 or (color[v] == 0 and dfs(v)):
return True
color[u] = 2
return False
return any(color[i] == 0 and dfs(i) for i in range(n))
Run a BFS topological sort. If you process fewer than n nodes, the leftover nodes are part of a cycle. This avoids recursion depth limits.
With union-find, an edge whose two endpoints already share a root closes a cycle. With DFS, skip the edge back to the parent and flag any other visited neighbor.
Written by the team at Linkjob, where we build AI tools for coding interview practice.