Builds on Flood Fill, which you haven’t finished yet.
Cycle Detection in a Directed Graph (DFS Three-Color)
Course Schedule (LC 207)(opens leetcode.com)
You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Decide whether every course can be completed at all — return true if a valid completion order exists, and false otherwise.
Cycle Detection
WHITE (0=unvisited) ➔ GREY (1=visiting) ➔ BLACK (2=processed)| 1 | from typing import List |
| 2 | |
| 3 | def has_cycle_directed(n: int, edges: List[List[int]]) -> bool: |
| 4 | """Directed cycle detection with three colors (the check behind Course Schedule). |
| 5 | Time: O(V + E) | Space: O(V + E) |
| 6 | """ |
| 7 | WHITE, GREY, BLACK = 0, 1, 2 |
| 8 | state = [WHITE] * n |
| 9 | adj = [[] for _ in range(n)] |
| 10 | for u, v in edges: |
| 11 | adj[u].append(v) |
| 12 | |
| 13 | def dfs(u: int) -> bool: |
| 14 | state[u] = GREY # On the active path |
| 15 | for v in adj[u]: |
| 16 | if state[v] == GREY: |
| 17 | return True # Edge back into the active path: cycle |
| 18 | if state[v] == WHITE and dfs(v): |
| 19 | return True |
| 20 | state[u] = BLACK # All neighbours done: u can't reach a cycle |
| 21 | return False |
| 22 | |
| 23 | for node in range(n): |
| 24 | if state[node] == WHITE and dfs(node): |
| 25 | return True |
| 26 | return False |
GREY nodes are exactly the nodes on the current DFS path, and every node reachable from a BLACK node is BLACK and on no cycle.Give every node a state: WHITE = not visited, GREY = on the current DFS path, BLACK = finished. Reaching a GREY node from u means an edge back into the path that led to u, so that path and the edge form a cycle. A node turns BLACK only after all its neighbours return without finding one, so a BLACK node can't lead to a cycle and is never searched again. The trap is using one visited flag: reaching a BLACK node again through a second path is not a cycle, so GREY and BLACK must stay different.
See it run
Three states in a depth-first search, step by step
state [0, 0, 0, 0, 0, 0, 0]
Each circle is a node and each arrow is an edge. State 0 is not seen, state 1 is on the current path, state 2 is finished. A node in state 0 is drawn plain.
nowthe node whose edges are being read, or the edge being followedpathstate 1: a node of the current depth-first pathdonestate 2: every neighbour returned without a cyclebackan edge into a node that is on the current pathunsafea node on a path that ended in a cycle, left out of state 2
Every node starts in state 0 (not seen). The outer loop will call dfs on each node that is still in state 0.
Gotcha 1 of 4
- The trap
Gotcha 1: Reporting a cycle at any visited node,
BLACKincludedMistakeif state[v] != WHITE:Fixif state[v] == GREY:What happens: A
BLACKnode is finished, and no cycle runs through it. A second path can still reach it, as in a diamond 0 -> 1 -> 3 and 0 -> 2 -> 3. A single visited flag treats that second visit as a cycle. Only aGREYnode, one on the current path, closes a cycle.Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]]Mistake: returns TrueFix: returns False
- You need the number of rounds when every task whose prerequisites are done runs at the same time, as in Parallel Courses (LC 1136), not just whether a cycle exists. See Topological Sort
- Every node has exactly one next pointer and memory must stay
O(1), as in Linked List Cycle (LC 141). See Fast & Slow Pointers
Deep Dive
Why a node on the current path closes a cycle
Each node has one of three states in state. WHITE (0) means not seen. GREY (1) means the node is on the current depth-first path, so dfs was called on it and has not returned. BLACK (2) means dfs has returned for it, and no cycle was found below it.
The nodes in state GREY are exactly the chain of calls that led to u: each one has an edge to the next one. Suppose u has an edge to a node v that is GREY. Then v is an ancestor of u on the path, and the path from v down to u plus the edge u -> v is a cycle.
A BLACK node is different. All of its neighbours returned without a cycle, so no cycle starts at it. Another path may reach it again, as in a diamond with the edges 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3. The second visit to node 3 is not a cycle. So GREY and BLACK must be different states, and only GREY is a cycle.
Example: in Find Eventual Safe States (LC 802), a node is safe when every path from it ends at a node with no outgoing edge. With graph = [[1,2],[2,3],[5],[0],[5],[],[]], the edges 0 -> 1, 1 -> 3 and 3 -> 0 form a cycle. The safe nodes are [2, 4, 5, 6].
One trace: the path, the back edge and the safe nodes
The board replays the example above. For Find Eventual Safe States (LC 802), the search does not stop at the first cycle. It returns True up the path and goes on with the next node in the outer loop.
The search starts at node 0 and follows 0 -> 1, 1 -> 2 and 2 -> 5. Node 5 has no neighbour, so it becomes state 2. Then node 2 becomes state 2. Back at node 1, the edge 1 -> 3 leads to node 3, and node 3 has the edge 3 -> 0.
Node 0 is in state 1, because dfs(0) has not returned. The edge 3 -> 0 is the back edge, and dfs(3) returns True. The nodes 3, 1 and 0 stay in state 1 and never reach state 2. The board calls them unsafe.
The outer loop then starts dfs(4). The edge 4 -> 5 leads to a node in state 2, so it is not a cycle, and node 4 becomes state 2. Node 6 has no neighbour and becomes state 2. The nodes in state 2 are [2, 4, 5, 6], which is the LeetCode answer.
The trap: one visited flag is not enough
Suppose the test is if state[v] != WHITE, which treats every seen node as a cycle. In the trace, the edge 4 -> 5 reaches node 5, which is finished. The flag version reports a cycle there, and node 4 is marked unsafe. The result is [2, 5, 6] and not [2, 4, 5, 6].
The same fault appears in the diamond. Course Schedule (LC 207) with the prerequisites of a diamond has no cycle. The flag version says it has one. The correct test is if state[v] == GREY.
The order of the state changes matters too. u must become GREY before its neighbours are searched, and BLACK only after the loop over its neighbours. If u is set to BLACK at the start, no node is ever GREY, and [[0, 1], [1, 0]] is reported as having no cycle.
Do not use this on an undirected graph. An undirected edge is stored in both directions, so the search from v sees the edge back to its parent u, which is GREY. Every edge looks like a cycle. An undirected graph needs a parent check or Union-Find.
The cost, and the neighbouring cards
Each node is entered once, because dfs is called only on a WHITE node and turns it to GREY at once. Each edge is read once, when its first node is processed. The time is O(V + E), and the space is O(V + E) for adj and state, plus the recursion stack of up to V calls.
The recursion depth is the length of the longest path. Course Schedule (LC 207) allows 2000 courses in one chain, which is 2000 nested calls. Python's default limit is 1000, so raise it with sys.setrecursionlimit, or keep the three states on an explicit stack.
Peel Dependencies answers the same question about a cycle with a queue and in-degrees, and it also gives the order of the tasks, as in Course Schedule II (LC 210). Use it when the order or the number of rounds is asked, as in Parallel Courses (LC 1136). Use the three states when you need to know which nodes lead to a cycle, as in Find Eventual Safe States (LC 802).
When every node has exactly one next pointer and memory must stay O(1), as in Linked List Cycle (LC 141), Tortoise and Hare is the better tool.
60-Second Pitch
"For a cycle in a directed graph, I give each node one of three states: not seen, on the current path, or finished. dfs(u) marks u as on the path, then looks at each neighbour. A neighbour that is on the path means an edge back into the path, so there is a cycle. A neighbour that is not seen gets its own dfs. A finished neighbour is skipped, because it cannot reach a cycle. After all neighbours return, I mark u finished. A finished node is never searched again, so each node and edge is read once. The time is O(V + E). I need two different states for on the path and finished. With one visited flag, a diamond looks like a cycle. For safe nodes, the nodes that end finished are the answer."
Common Questions
- Why do you need three states and not a simple visited set?
A visited set cannot tell a node on the current path from a node that is finished. Only an edge into the current path is a cycle. An edge into a finished node is fine, as in a diamond. The third state records that difference.
- What are the time and space complexity?
O(V + E)time, because each node gets onedfscall and each edge is read once.O(V + E)space for the adjacency list and the states, plus a recursion stack that is as deep as the longest path, up to V calls.- How do you get the safe nodes in Find Eventual Safe States (LC 802)?
Run the search from every node that is not seen, and do not stop at the first cycle. When
dfsreturns True, leave the nodes of the path in state 1. At the end, the safe nodes are the ones in state 2, in increasing order. Another way is to reverse the edges and peel nodes whose neighbours are all safe, which is the Peel Dependencies idea.- Why does the check
state[v] == GREYnot work on an undirected graph? An undirected edge is stored in both directions. When the search goes from
utov, the edge fromvback toufindsuin state 1. That is the edge the search just came along, and it is not a cycle. A parent check or Union-Find is needed.
SWE Reasoning
Spot it
- The graph is directed, and the task asks whether a cycle exists.
- The wording says safe nodes, nodes that cannot reach a cycle, or "every path ends properly".
- Dependencies or prerequisites are given as pairs, and the task asks whether all of them can be met.
- You need to know which nodes lead to a cycle, and not only whether one exists.
- Reaching a node twice is allowed when it is not on the current path, as in a diamond.
The invariant, step by step
- Every node starts in state 0, not seen. The outer loop calls
dfson each node that is still in state 0. dfs(u)setsstate[u]to 1 first, so the nodes in state 1 are exactly the nodes on the current path.- For each neighbour
vofu: ifstate[v]is 1, the edge goes back into the path, so there is a cycle anddfsreturns True. - If
state[v]is 0,dfs(v)is called. If that call returns True, the answer is passed up at once. - If
state[v]is 2,vis finished and cannot reach a cycle. The edge is skipped. - After the loop over the neighbours,
state[u]becomes 2. A node in state 2 has every neighbour in state 2, so no cycle is reachable from it.
Traps
- One visited flag. Reaching a finished node again through a second path is not a cycle. Only state 1 is a cycle.
uset to state 2 before its neighbours are searched. No node is ever in state 1, so no cycle is found.- The three states on an undirected graph. Every edge looks like a cycle, because the edge back to the parent is found. Use a parent check or Union-Find.
- Python's default recursion limit. A chain of 2000 nodes makes 2000 nested calls. Raise the limit or use an explicit stack.
- Stopping at the first cycle when the question is about safe nodes. Keep going with the outer loop. The nodes that never reach state 2 are the unsafe ones.
Practice
Builds on Flood Fill, which you haven’t finished yet.
Cycle Detection in a Directed Graph (DFS Three-Color)
Course Schedule (LC 207)(opens leetcode.com)
You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Decide whether every course can be completed at all — return true if a valid completion order exists, and false otherwise.
Cycle Detection
WHITE (0=unvisited) ➔ GREY (1=visiting) ➔ BLACK (2=processed)| 1 | from typing import List |
| 2 | |
| 3 | def has_cycle_directed(n: int, edges: List[List[int]]) -> bool: |
| 4 | """Directed cycle detection with three colors (the check behind Course Schedule). |
| 5 | Time: O(V + E) | Space: O(V + E) |
| 6 | """ |
| 7 | WHITE, GREY, BLACK = 0, 1, 2 |
| 8 | state = [WHITE] * n |
| 9 | adj = [[] for _ in range(n)] |
| 10 | for u, v in edges: |
| 11 | adj[u].append(v) |
| 12 | |
| 13 | def dfs(u: int) -> bool: |
| 14 | state[u] = GREY # On the active path |
| 15 | for v in adj[u]: |
| 16 | if state[v] == GREY: |
| 17 | return True # Edge back into the active path: cycle |
| 18 | if state[v] == WHITE and dfs(v): |
| 19 | return True |
| 20 | state[u] = BLACK # All neighbours done: u can't reach a cycle |
| 21 | return False |
| 22 | |
| 23 | for node in range(n): |
| 24 | if state[node] == WHITE and dfs(node): |
| 25 | return True |
| 26 | return False |
GREY nodes are exactly the nodes on the current DFS path, and every node reachable from a BLACK node is BLACK and on no cycle.Give every node a state: WHITE = not visited, GREY = on the current DFS path, BLACK = finished. Reaching a GREY node from u means an edge back into the path that led to u, so that path and the edge form a cycle. A node turns BLACK only after all its neighbours return without finding one, so a BLACK node can't lead to a cycle and is never searched again. The trap is using one visited flag: reaching a BLACK node again through a second path is not a cycle, so GREY and BLACK must stay different.
See it run
Three states in a depth-first search, step by step
state [0, 0, 0, 0, 0, 0, 0]
Each circle is a node and each arrow is an edge. State 0 is not seen, state 1 is on the current path, state 2 is finished. A node in state 0 is drawn plain.
nowthe node whose edges are being read, or the edge being followedpathstate 1: a node of the current depth-first pathdonestate 2: every neighbour returned without a cyclebackan edge into a node that is on the current pathunsafea node on a path that ended in a cycle, left out of state 2
Every node starts in state 0 (not seen). The outer loop will call dfs on each node that is still in state 0.
Gotcha 1 of 4
- The trap
Gotcha 1: Reporting a cycle at any visited node,
BLACKincludedMistakeif state[v] != WHITE:Fixif state[v] == GREY:What happens: A
BLACKnode is finished, and no cycle runs through it. A second path can still reach it, as in a diamond 0 -> 1 -> 3 and 0 -> 2 -> 3. A single visited flag treats that second visit as a cycle. Only aGREYnode, one on the current path, closes a cycle.Example: n = 4, edges = [[0, 1], [0, 2], [1, 3], [2, 3]]Mistake: returns TrueFix: returns False
- You need the number of rounds when every task whose prerequisites are done runs at the same time, as in Parallel Courses (LC 1136), not just whether a cycle exists. See Topological Sort
- Every node has exactly one next pointer and memory must stay
O(1), as in Linked List Cycle (LC 141). See Fast & Slow Pointers
Deep Dive
Why a node on the current path closes a cycle
Each node has one of three states in state. WHITE (0) means not seen. GREY (1) means the node is on the current depth-first path, so dfs was called on it and has not returned. BLACK (2) means dfs has returned for it, and no cycle was found below it.
The nodes in state GREY are exactly the chain of calls that led to u: each one has an edge to the next one. Suppose u has an edge to a node v that is GREY. Then v is an ancestor of u on the path, and the path from v down to u plus the edge u -> v is a cycle.
A BLACK node is different. All of its neighbours returned without a cycle, so no cycle starts at it. Another path may reach it again, as in a diamond with the edges 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3. The second visit to node 3 is not a cycle. So GREY and BLACK must be different states, and only GREY is a cycle.
Example: in Find Eventual Safe States (LC 802), a node is safe when every path from it ends at a node with no outgoing edge. With graph = [[1,2],[2,3],[5],[0],[5],[],[]], the edges 0 -> 1, 1 -> 3 and 3 -> 0 form a cycle. The safe nodes are [2, 4, 5, 6].
One trace: the path, the back edge and the safe nodes
The board replays the example above. For Find Eventual Safe States (LC 802), the search does not stop at the first cycle. It returns True up the path and goes on with the next node in the outer loop.
The search starts at node 0 and follows 0 -> 1, 1 -> 2 and 2 -> 5. Node 5 has no neighbour, so it becomes state 2. Then node 2 becomes state 2. Back at node 1, the edge 1 -> 3 leads to node 3, and node 3 has the edge 3 -> 0.
Node 0 is in state 1, because dfs(0) has not returned. The edge 3 -> 0 is the back edge, and dfs(3) returns True. The nodes 3, 1 and 0 stay in state 1 and never reach state 2. The board calls them unsafe.
The outer loop then starts dfs(4). The edge 4 -> 5 leads to a node in state 2, so it is not a cycle, and node 4 becomes state 2. Node 6 has no neighbour and becomes state 2. The nodes in state 2 are [2, 4, 5, 6], which is the LeetCode answer.
The trap: one visited flag is not enough
Suppose the test is if state[v] != WHITE, which treats every seen node as a cycle. In the trace, the edge 4 -> 5 reaches node 5, which is finished. The flag version reports a cycle there, and node 4 is marked unsafe. The result is [2, 5, 6] and not [2, 4, 5, 6].
The same fault appears in the diamond. Course Schedule (LC 207) with the prerequisites of a diamond has no cycle. The flag version says it has one. The correct test is if state[v] == GREY.
The order of the state changes matters too. u must become GREY before its neighbours are searched, and BLACK only after the loop over its neighbours. If u is set to BLACK at the start, no node is ever GREY, and [[0, 1], [1, 0]] is reported as having no cycle.
Do not use this on an undirected graph. An undirected edge is stored in both directions, so the search from v sees the edge back to its parent u, which is GREY. Every edge looks like a cycle. An undirected graph needs a parent check or Union-Find.
The cost, and the neighbouring cards
Each node is entered once, because dfs is called only on a WHITE node and turns it to GREY at once. Each edge is read once, when its first node is processed. The time is O(V + E), and the space is O(V + E) for adj and state, plus the recursion stack of up to V calls.
The recursion depth is the length of the longest path. Course Schedule (LC 207) allows 2000 courses in one chain, which is 2000 nested calls. Python's default limit is 1000, so raise it with sys.setrecursionlimit, or keep the three states on an explicit stack.
Peel Dependencies answers the same question about a cycle with a queue and in-degrees, and it also gives the order of the tasks, as in Course Schedule II (LC 210). Use it when the order or the number of rounds is asked, as in Parallel Courses (LC 1136). Use the three states when you need to know which nodes lead to a cycle, as in Find Eventual Safe States (LC 802).
When every node has exactly one next pointer and memory must stay O(1), as in Linked List Cycle (LC 141), Tortoise and Hare is the better tool.
60-Second Pitch
"For a cycle in a directed graph, I give each node one of three states: not seen, on the current path, or finished. dfs(u) marks u as on the path, then looks at each neighbour. A neighbour that is on the path means an edge back into the path, so there is a cycle. A neighbour that is not seen gets its own dfs. A finished neighbour is skipped, because it cannot reach a cycle. After all neighbours return, I mark u finished. A finished node is never searched again, so each node and edge is read once. The time is O(V + E). I need two different states for on the path and finished. With one visited flag, a diamond looks like a cycle. For safe nodes, the nodes that end finished are the answer."
Common Questions
- Why do you need three states and not a simple visited set?
A visited set cannot tell a node on the current path from a node that is finished. Only an edge into the current path is a cycle. An edge into a finished node is fine, as in a diamond. The third state records that difference.
- What are the time and space complexity?
O(V + E)time, because each node gets onedfscall and each edge is read once.O(V + E)space for the adjacency list and the states, plus a recursion stack that is as deep as the longest path, up to V calls.- How do you get the safe nodes in Find Eventual Safe States (LC 802)?
Run the search from every node that is not seen, and do not stop at the first cycle. When
dfsreturns True, leave the nodes of the path in state 1. At the end, the safe nodes are the ones in state 2, in increasing order. Another way is to reverse the edges and peel nodes whose neighbours are all safe, which is the Peel Dependencies idea.- Why does the check
state[v] == GREYnot work on an undirected graph? An undirected edge is stored in both directions. When the search goes from
utov, the edge fromvback toufindsuin state 1. That is the edge the search just came along, and it is not a cycle. A parent check or Union-Find is needed.
SWE Reasoning
Spot it
- The graph is directed, and the task asks whether a cycle exists.
- The wording says safe nodes, nodes that cannot reach a cycle, or "every path ends properly".
- Dependencies or prerequisites are given as pairs, and the task asks whether all of them can be met.
- You need to know which nodes lead to a cycle, and not only whether one exists.
- Reaching a node twice is allowed when it is not on the current path, as in a diamond.
The invariant, step by step
- Every node starts in state 0, not seen. The outer loop calls
dfson each node that is still in state 0. dfs(u)setsstate[u]to 1 first, so the nodes in state 1 are exactly the nodes on the current path.- For each neighbour
vofu: ifstate[v]is 1, the edge goes back into the path, so there is a cycle anddfsreturns True. - If
state[v]is 0,dfs(v)is called. If that call returns True, the answer is passed up at once. - If
state[v]is 2,vis finished and cannot reach a cycle. The edge is skipped. - After the loop over the neighbours,
state[u]becomes 2. A node in state 2 has every neighbour in state 2, so no cycle is reachable from it.
Traps
- One visited flag. Reaching a finished node again through a second path is not a cycle. Only state 1 is a cycle.
uset to state 2 before its neighbours are searched. No node is ever in state 1, so no cycle is found.- The three states on an undirected graph. Every edge looks like a cycle, because the edge back to the parent is found. Use a parent check or Union-Find.
- Python's default recursion limit. A chain of 2000 nodes makes 2000 nested calls. Raise the limit or use an explicit stack.
- Stopping at the first cycle when the question is about safe nodes. Keep going with the outer loop. The nodes that never reach state 2 are the unsafe ones.