AI Hints
Home›DSA in Python Tutorial›More Practice: Backtracking and Graphs
DSA in Python · Lesson 122 of 132

Practice: Detect a Cycle

Three colours.

⏱ 2 min read▶ Video at 2:25:27🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Detect a Cycle
From the video: Practice: Detect a Cycle
  • 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.

cycle.pypython
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": []}))
Output
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.

keyvalue
Whitenot visited
Greyon the current path
Blackfinished
Grey againa 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)
Next up: Practice: Top K Frequent Words — Counter and a heap