Detect Cycles in Directed Graphs
Color nodes to find back edges.
Detect Cycles in Directed Graphs is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Cycles Matter
A directed cycle means dependencies loop back on themselves. Spotting one tells you no topological order or valid schedule can exist.
Undirected Is Different
Cycle detection here is about direction. Following edges the wrong way does not count, so undirected tricks do not apply.
The Three-Color Idea
Give each node one of three colors: white means unvisited, gray means in progress, black means fully done.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGray Means On the Stack
A gray node sits on your current DFS path. You entered it but have not finished exploring all its descendants yet.
Enter a Node
When DFS reaches a node, paint it gray before exploring. That marks it as part of the active path.
def dfs(u):
color[u] = GRAYThe Back Edge Signal
If you reach a neighbor that is already gray, you found a back edge into the current path. That is a cycle.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleRecurse Into White
A white neighbor is fresh, so recurse into it. Bubble up True the moment any deeper call reports a cycle.
elif color[v] == WHITE and dfs(v):
return TrueBlack Is Safe
A black neighbor is fully explored and cycle-free, so you can ignore it. Revisiting it would only waste time.
Finish a Node
After all neighbors are handled, paint the node black. It leaves the active path and is marked complete.
color[u] = BLACK
return FalseCover Every Component
The graph may be disconnected, so start DFS from every still-white node to be sure you check all of it.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Mind the Recursion Limit
Deep graphs can overflow Python's recursion stack. Raise the limit or rewrite the DFS with an explicit stack.
import sys
sys.setrecursionlimit(300000)Quick Check
During DFS you reach a neighbor that is currently gray. What did you just find?
Recap: Cycle Detection
Color nodes white, gray, then black. A gray neighbor during DFS is a back edge, which proves a directed cycle. 🔁
Frequently asked questions
Is the “Detect Cycles in Directed Graphs” lesson free?
Yes — the full text of “Detect Cycles in Directed Graphs” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Detect Cycles in Directed Graphs”?
Color nodes to find back edges. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Detect Cycles in Directed Graphs” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Topological Sort with Kahn's Algorithm
- Detect Cycles in Directed Graphs
- Strongly Connected Components
- Bridges & Articulation Points