Practice: Detect a Cycle
Three colours.
In a directed graph of tasks, a cycle means task A needs B, B needs C, and C needs A. Nothing could ever start. How do we detect a cycle with depth first search?

- A needs B, B needs C, C needs A
- Nothing can start
- Detect it with DFS
White, grey, black
Each node starts white, unvisited. While we're exploring a node's descendants, it's grey. When we're finished with it, it turns black. If depth first search ever reaches a grey node, we've walked in a circle. Run it. The first graph has a cycle, and the second doesn't.
def has_cycle(graph):
colour = {node: "white" for node in graph}
def dfs(node):
colour[node] = "grey"
for nxt in graph[node]:
if colour[nxt] == "grey":
return True
if colour[nxt] == "white" and dfs(nxt):
return True
colour[node] = "black"
return False
return any(colour[n] == "white" and dfs(n) for n in graph)
print(has_cycle({"A": ["B"], "B": ["C"], "C": ["A"]}))
print(has_cycle({"A": ["B", "C"], "B": ["C"], "C": []}))True False
Why grey matters
A black node was fully explored, and it led to no cycle, so reaching it again is fine. Only grey nodes are still on the current path. That's why we need three colours, not just visited or not. For undirected graphs, a simpler check works, using union find, or the parent of each node.
| key | value |
|---|---|
| White | not visited |
| Grey | on the current path |
| Black | finished |
| Grey again | a cycle |
Summary
Colour nodes white, grey, and black. Reaching a grey node means a cycle. Next, the most common words, with a counter and a heap.
Key takeaways- Three colours
- Grey means on the path
- O(V + E)