DFS three-colour cycle detection

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four courses have prerequisites: course 0 must be done before 1, 1 before 2, 2 before 3, and 3 before 1. Can you finish them all? Try to plan it: 0 first, then 1, then 2, then 3, but 3 must come before 1, which you already did. No order works. The rule 1 → 2 → 3 → 1 is a loop, and a loop of prerequisites can never be satisfied.

By hand you spot the loop by staring. With 4 courses that is easy. With 2,000 courses and 10,000 prerequisites you cannot stare, and trying every order is hopeless: 2,000 courses have more orders than there are atoms in the universe. We need a walk through the graph that notices a loop the moment it closes.

Build the structure, one piece at a time

First, a graph: each course is a node, each prerequisite "a before b" is an arrow a → b. Store it as a list of outgoing arrows per node: 0: [1], 1: [2], 2: [3], 3: [1].

Second, depth-first search: from a node, follow one arrow as far as it goes before trying the next. A plain visited mark (yes or no) is not enough, because reaching a node you have seen before could mean two different things: it finished long ago, or it is still being explored on the path you are walking right now. Only the second case is a loop.

So give every node one of three colours instead of two:

1. white: never entered;
2. grey: entered, and we are still inside its exploration (it is on the current path);
3. black: fully finished.

Walk the example. Enter 0: grey = {0}. Follow 0 → 1, enter 1: grey = {0, 1}. Follow 1 → 2: grey = {0, 1, 2}. Follow 2 → 3: grey = {0, 1, 2, 3}. Now 3 → 1, and 1 is grey. The path we are standing on already contains 1, so walking to it closes a loop: 1 → 2 → 3 → 1. Cycle found. Had 1 been black, the arrow would be harmless: 1 finished without ever reaching us.

Why it is correct

The invariant: the grey nodes are exactly the nodes on the current path from the starting node. It holds because a node turns grey when we step onto it and black when we step off it, and depth-first search steps off nodes in the reverse order it stepped on, like a stack.

So an arrow into a grey node is an arrow from the end of the current path back into the middle of it, which is a cycle by definition. Conversely, if there is a cycle, consider the first node of that cycle the search enters; before that node turns black, the search must follow the cycle round and arrive at it while it is still grey. So a cycle is always caught, and only cycles are reported.

Why it is fast

Each node is coloured grey once and black once, and each arrow is looked at once, when its source is being explored. With V nodes and E arrows:

work = V + E

For 2,000 courses and 10,000 prerequisites that is about 12,000 steps, against the astronomically many orders a brute-force attempt would try.

How to recognise it in an interview

Cues: "prerequisites", "depends on", "can all tasks be finished", "detect a cycle in a directed graph", "which nodes always end in a dead end". The first thing to say: "I will DFS with three colours; an arrow into a grey node is a cycle." Course Schedule asks exactly whether the prerequisite graph is cycle-free. Find Eventual Safe States is the same walk with a different reading of the colours: a node is safe if every path from it ends in black without ever meeting grey.

02The idea in one line

White unvisited, grey on the current path, black done; a grey neighbour means a cycle.

Reach for it when: Course schedule, eventual safe states, detect cycle in directed graph.

Cost: O(V + E) time.

03The walk-through, step by step

The video works one example: Course Schedule with a 1→2→3→1 cycle. These are its captions in order, so you can follow without the video or check a step you missed.

1. Can every course be taken? Only if the prerequisite graph has no cycle
2. Three colours: grey means 'still on the recursion stack'
3. Enter 0: mark it grey
4. Enter 1: mark it grey
5. Enter 2: mark it grey
6. Enter 3: mark it grey
7. 3→1 but 1 is grey: it is on the current path, cycle found
8. A black neighbour would be fine: it finished without reaching us
9. 1→2→3→1 is a cycle, so the courses cannot all be finished
10. Each node coloured once, each edge checked once: O(V + E)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).