Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Run DFS and track which nodes are on the *current* recursion path. Mark each node with three states: white (unvisited), gray (in progress, on the path), black (done). An edge to a gray node is a back edge — that is a cycle. Equivalently, run Kahn's topological sort and check that you processed all n nodes; if some stay stuck, they sit inside a cycle. Both run in O(V + E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know a two-state visited set is not enough for directed graphs, and can articulate why the in-progress (gray) state is the whole trick.
Where candidates slip
Reusing the undirected approach: a single visited set that flags any re-seen node as a cycle — which wrongly fires on a diamond (a node reached via two paths but with no cycle).
How to stand out
Name the back-edge definition, present both DFS three-color and Kahn's BFS, and explain that the gray state is just the recursion stack made explicit.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewDirected graph: any cycle?Want a topo order too?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
DFS with Three-Color Marking (Optimal)
1Hint 1Explore hintHide hint
A directed cycle means that while walking a path you arrive back at a node you are *still in the middle of exploring*. How would you mark 'currently exploring'?
2Hint 2Explore hintHide hint
Give each node three states: white (untouched), gray (entered, on the current path), black (fully finished). Paint gray on entry, black after all children return.
3Hint 3Explore hintHide hint
If DFS follows an edge to a gray node, that's a back edge → cycle → true. An edge to a black node is a finished subtree and is safe to ignore.
A · Core idea
Walk the graph depth-first and watch for an edge that points back into the path you are currently on.
Why a two-state visited set fails. In an undirected graph a boolean visited set works, but directed graphs need more. Picture a diamond 0→1, 0→2, 1→3, 2→3: node 3 is reached twice, yet there is no cycle. A two-state set would see the second arrival at 3 and falsely shout 'cycle'. The missing distinction is whether the re-seen node is still open on the current recursion stack or already finished.
The three colors. White (0) means untouched. Gray (1) means you have entered the node and are still exploring its descendants — it sits on the active recursion stack right now. Black (2) means the node and its whole subtree are done. You paint a node gray the moment DFS enters it and black only after every child call returns.
The cycle rule. While exploring node u, if you follow an edge to a node that is currently gray, you have looped back to an ancestor still on your path. That is a back edge, and a back edge is the exact definition of a directed cycle — so return true. If the target is black, it is a finished subtree (like 3 in the diamond) and you safely skip it.
Why the driver loops over all nodes. The graph can be disconnected, so a single DFS launch might never reach some component. You start a fresh DFS from every white node; if any of them reports a cycle, the answer is true.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[0,1],[1,2],[2,0],[2,3]]Interactive diagram
Back edge into a gray node
dfs(0)0, 1, 2 are all gray (on the path) when the edge 2→0 fires — that back edge is the cycle.
trueC · Code with teaching comments
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
The gray set is the recursion stack made visible: a node is gray for exactly the span it sits on the active call chain. A directed cycle is nothing more than an edge that points back up that chain — so 'edge to a gray node' is the complete, precise test, no more and no less.
ComplexityO(V + E) time, O(V + E) space — Each node is painted gray once and black once, so it's entered a constant number of times: O(V). Each edge is examined once when its source is gray: O(E). Total O(V + E). The color array and adjacency list are O(V + E); recursion depth is O(V) in the worst case.
E · Edge cases and pitfalls7self-loop n=1, edges=[[0,0]] — dfs(0) paints 0 gray, then edge 0→0 sees gray → cycle → true.Explore edge casesHide edge cases
Edge cases handled
self-loop n=1, edges=[[0,0]]dfs(0) paints 0 gray, then edge 0→0 sees gray → cycle → true.diamond 0→1,0→2,1→3,2→3Node 3 is black on the second visit → no false cycle → false.n=3, edges=[] (no edges)Every node finishes black with no neighbours → false.two components, cycle only in the secondDriver loop launches DFS from the second component's nodes and finds the cycle → true.
Pitfalls
- Using a single boolean visited set — falsely flags diamond joins as cycles.
- Painting a node black before its children finish — misses real back edges.
- Launching DFS from only node 0 — disconnected components with cycles slip through.
Approach 2 of 2
Kahn's Algorithm — Indegree BFS (Iterative Alternative)
1Hint 1Explore hintHide hint
Which nodes can never be part of a cycle's 'entry'? Those with indegree 0 — nothing points at them. What happens when you remove them?
2Hint 2Explore hintHide hint
Compute every node's indegree, queue all indegree-0 nodes, and repeatedly pop one, decrementing its neighbours' indegrees.
3Hint 3Explore hintHide hint
Count how many nodes you pop. If a cycle exists, its nodes keep each other's indegree above 0 forever, so the count falls short of n.
A · Core idea
Topologically peel the graph and let a leftover count expose the cycle.
Indegree counts unremoved incoming edges. A node with indegree 0 has nothing pointing into it, so it can be 'taken' immediately. Seed a queue with all such nodes.
Removing a node unlocks its successors. Popping node u removes its outgoing edges, so each neighbour v loses one incoming edge — decrement indegree[v]. When v reaches 0, it too becomes free and joins the queue. This drains the DAG layer by layer.
A cycle blocks its own removal. Every node inside a directed cycle has at least one incoming edge from another cycle member, so its indegree never reaches 0 and it never enters the queue. Count the popped nodes: in an acyclic graph all n are processed; if a cycle traps some, the count is below n. So processed < n means a cycle exists.
Free topological order. The pop sequence is a valid topological ordering when no cycle exists — which is why this method doubles as topological sort.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[0,1],[1,2],[2,0],[2,3]]Array state
initial
indeg of 0..3
trueC · Code with teaching comments
Reference implementation previewpublic boolean hasCycle(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int[] indeg = new int[n]; for (int[] e : edges) {Explore the full codeHide the full code
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Kahn's turns 'is there a cycle?' into 'can I peel every node by always removing one with no incoming edges?'. A cycle is a knot that can never be peeled, so the unprocessed remainder is the cycle's fingerprint.
ComplexityO(V + E) time, O(V + E) space — Building the adjacency list and indegrees is O(V + E). Each node enters and leaves the queue once (O(V)), and each edge is relaxed once when its source is popped (O(E)). Total O(V + E); the queue, indegree array, and graph are O(V + E) space.
E · Edge cases and pitfalls3Returning processed == n for 'has cycle' — that's inverted; a full peel means NO cycle.Explore edge casesHide edge cases
Pitfalls
- Returning processed == n for 'has cycle' — that's inverted; a full peel means NO cycle.
- Decrementing indegree of the source instead of the target.
- Forgetting to seed all indegree-0 nodes, stranding disconnected components.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean hasCycle(int n, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) adj.get(e[0]).add(e[1]); int[] color = new int[n]; // 0 white, 1 gray, 2 blackExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Two-state visited set instead of three colors
A boolean visited set can't separate 'still on the path' from 'already done', so a diamond's join node — reached twice with no cycle — is wrongly flagged.
Explore the code comparisonHide the code comparison
Two-state visited set instead of three colors
A boolean visited set can't separate 'still on the path' from 'already done', so a diamond's join node — reached twice with no cycle — is wrongly flagged.
Don't write this
visited = set()
def dfs(u):
if u in visited:
return True # WRONG: a finished join looks like a cycle
visited.add(u)
for v in adj[u]:
if dfs(v): return True
return FalseWrite this instead
color = [0] * n # 0 white, 1 gray, 2 black
def dfs(u):
color[u] = 1
for v in adj[u]:
if color[v] == 1: return True # back edge only
if color[v] == 0 and dfs(v): return True
color[u] = 2
return False2Black painted too early
If you mark a node black on entry instead of after its children finish, an edge that should see gray sees black and the cycle is missed.
Explore the code comparisonHide the code comparison
Black painted too early
If you mark a node black on entry instead of after its children finish, an edge that should see gray sees black and the cycle is missed.
Don't write this
private boolean dfs(int u) {
color[u] = 2; // WRONG: marked done immediately
for (int v : adj.get(u)) {
if (color[v] == 0 && dfs(v)) return true;
}
return false;
}Write this instead
private boolean dfs(int u) {
color[u] = 1; // gray on entry
for (int v : adj.get(u)) {
if (color[v] == 1) return true;
if (color[v] == 0 && dfs(v)) return true;
}
color[u] = 2; // black after children
return false;
}Revise
Carry the pattern into the interview
Pattern to remember
Directed cycle = back edge to a node still on the DFS recursion stack (gray node)
Code pattern to memorize
WHITE=0, GRAY=1, BLACK=2
dfs(u):
color[u] = GRAY
for v in adj[u]:
if color[v] == GRAY: return True # back edge → cycle
if color[v] == WHITE and dfs(v): return True
color[u] = BLACK
return FalseRules to remember
- 1You need three states, not a two-state visited set. A plain boolean can't tell 'on the current path' from 'finished'.
- 2Paint a node gray on entry, black only after all its children return. The gray window is exactly its time on the recursion stack.
- 3An edge to a gray node is a cycle. An edge to a black node is a finished subtree — safe, skip it.
- 4Loop the DFS over every node — a directed graph can be disconnected, so one start node may miss whole components.
- 5If the iterative Kahn's version processes fewer than n nodes, the leftover nodes form the cycle.
Use this pattern when
- Dependency / prerequisite graphs where a deadlock = cycle
- Detecting deadlocks in resource-allocation or build systems
- Validating that a directed graph is a DAG before topologically sorting it
- Spotting infinite loops in state machines or call graphs
Choose another pattern when
- Undirected graph → use DFS-with-parent or Union-Find, not the gray/black trick
- You also need the actual ordering → Kahn's topological sort returns it for free
- Weighted shortest path → Dijkstra/Bellman-Ford, not cycle detection
- Counting connected components → plain visited DFS suffices
Interview takeaway
Directed cycle detection is the gray-node story: a cycle is precisely an edge back to a node still open on your recursion stack. The same three-color DFS underlies topological sort, Course Schedule, and deadlock detection.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternThree-color DFS for directed cycle detection: gray = on the recursion stack, and an edge to a gray node is a back edge. Kahn's BFS gives the same answer iteratively via a processed-count shortfall. Same family as Course Schedule, Find Eventual Safe States, and topological sort.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Course ScheduleSame cycle test phrased as 'can you finish all courses?' — true iff the prerequisite graph is acyclic.
- Course Schedule IIReturn the topological order; Kahn's pop sequence is the answer (empty list if a cycle exists).
- Find Eventual Safe StatesComing soonA node is safe iff no path from it reaches a cycle — three-color DFS marks unsafe (gray-reaching) nodes.
- Graph Valid TreeThe undirected cousin: detect cycles with DFS-and-parent or Union-Find, plus a connectivity check.