When DFS explores a directed graph, every edge it encounters falls into one of four categories based on the relationship between the source node and the destination node in the DFS tree.

Tree edges are the ones DFS follows to discover new nodes -- they form the DFS tree itself. Back edges point from a node to one of its ancestors in the DFS tree -- and these are the only edges that indicate a cycle. Forward edges point from an ancestor to a descendant that was already discovered through another path. Cross edges connect nodes in different branches of the DFS tree, where neither is an ancestor of the other.

Only back edges create cycles. A back edge says "I am pointing to a node that is still being processed -- a node that is above me on the current recursion stack." That creates a loop: the ancestor leads (through tree edges) down to the current node, and the back edge leads from the current node back up to the ancestor. That is a cycle.

The critical question: how do you distinguish a back edge from a cross or forward edge? Both point to already-visited nodes. The difference is whether the destination is still “in progress” (on the current recursion stack) or “finished” (fully processed and returned from). A simple boolean visited flag cannot tell the difference. You need something more.

Most people start cycle detection like this: if (visited[neighbor]) return true. It is intuitive -- if DFS encounters a node it has already seen, that must be a cycle, right?

For undirected graphs, this logic works (with a small caveat about the parent node). But for directed graphs, it is a trap that produces false positives -- reporting cycles in graphs that are perfectly acyclic.

Here is why. In a directed graph, DFS might finish exploring node X completely, mark it visited, backtrack, then later encounter X again from a different branch. The edge to X is a cross edge or forward edge -- completely harmless. But the boolean check sees visited[X] === true and screams “cycle!” It cannot distinguish “X is on my current path” (a real cycle) from “X was fully explored in an earlier branch” (no cycle).

A DAG (Directed Acyclic Graph) is the perfect showcase for this bug. DAGs have no cycles by definition, yet the boolean approach will flag false positives whenever two branches converge on the same node. And convergence is common in DAGs -- it is what makes them useful.

Step through this DAG below and watch the false positive happen. Notice the exact moment the boolean check incorrectly reports a cycle.

// Naive cycle detection

if (visited[neighbor]) return true; // cycle?

Same graph. This time you are running DFS with only a visited boolean, and at two critical moments you hit a node that is already marked visited. You must decide: is this a genuine cycle (a back edge to an ancestor on your current path), or just a harmless revisit to a fully-finished node (a cross edge)?

The boolean tells you nothing about when the node was visited or whether it is still being processed. You are flying blind. One of these moments is a real cycle -- following that edge would loop you back to an ancestor. The other is a trap -- the node was completely processed in an earlier branch and poses no danger.

This is the exact ambiguity that the three-color model resolves. But before you learn the fix, feel the problem. Try to distinguish the two cases using only “visited or not.” Notice how the boolean gives you the same answer for both, even though the correct responses are opposite.

Now you know the three-color rule. The classification is mechanical once you see it:

• Edge to a white neighbor: this node has never been visited. DFS will recurse into it, making this a tree edge -- part of the DFS tree itself.
• Edge to a gray neighbor: this node is currently on the recursion stack. It is an ancestor of the current node, and the edge from here back to it creates a loop. This is a back edge -- the only type that signals a cycle.
• Edge to a black neighbor: this node was fully processed and returned from. DFS already explored all its descendants. This is a cross edge or forward edge -- safe to ignore.

The color tells you everything. Gray means “I'm still in progress, and you're about to close a loop.” Black means “I'm done -- move along.” White means “I'm new -- come explore me.”

Test your intuition below. Given the source and target colors, classify each edge. Remember: gray-to-gray is the cycle signal.

For each edge below, look at the destination node's color and classify the edge. This is the exact check that runs inside the DFS loop: one if statement on the neighbor's color determines whether you recurse, report a cycle, or skip.

Here is a real directed cycle detection implementation. It looks clean -- descriptive variable names, clear structure, correct traversal logic. It even produces the right answer on graphs that do have cycles. The bug only surfaces on graphs that do not have cycles: it reports false positives.

The root cause is the boolean-visited trap you just experienced. Somewhere in this code, a node is being checked with a binary visited flag instead of the three-color model. The check conflates “in-progress ancestor” with “fully-finished node,” causing DFS to report a back edge where only a cross edge exists.

Two phases: first, find the line where the boolean check happens. Then pick the fix that replaces it with the correct three-color logic. The fix adds exactly one concept -- tracking whether a node is “in progress” versus “complete” -- but it eliminates every false positive.

LeetCode 207: Given numCourses and a list of prerequisites, determine if you can finish all courses. Each prerequisite pair [a, b] means “you must take course b before course a” -- a directed edge from b to a in the prerequisite graph.

If the prerequisite graph has a cycle, it is impossible to finish all courses. Course A requires B, B requires C, and C requires A -- no matter where you start, you are stuck in a loop. This is exactly the problem three-color DFS was designed for.

The algorithm: build the directed graph from the prerequisite list, then run three-color DFS. If any back edge is found (a gray-to-gray encounter), return false -- the cycle makes course completion impossible. If DFS finishes without finding a back edge, every node turns black, and the answer is true.

This is one of the most common graph problems in technical interviews. The insight that “course scheduling is cycle detection on a directed graph” is the bridge between abstract graph theory and practical problem-solving. Every time you see “can you order these things given these constraints,” think: directed graph, cycle detection, three colors.

Step through the 3-color DFS to find if these courses have a valid ordering.

Cycle detection in directed and undirected graphs looks similar on the surface -- both involve DFS and checking for already-visited nodes. But the algorithms are genuinely different, and using the wrong one produces incorrect results.

Undirected cycle detection is simpler. Every edge is bidirectional, so when DFS visits node A and then moves to neighbor B, B's neighbor list includes A. You need to avoid flagging this trivial “parent edge” as a cycle. The rule: if DFS encounters a visited node that is not the parent of the current node, that is a cycle. A simple parent parameter in the recursive call is enough.

Directed cycle detection requires the three-color model. The “parent” trick does not work because edges are one-way. A visited node might be an ancestor (back edge = cycle) or a node from a completely different branch (cross edge = safe). Only the gray/black distinction resolves this.

The practical consequence: if you use the undirected algorithm on a directed graph, you miss cycles. If you use the directed algorithm on an undirected graph, you report false positives (every undirected edge looks like a back edge). Always match the algorithm to the graph type.

Tap each panel below to see the difference in action on the same graph structure with directed versus undirected edges.

You stepped through the three-color algorithm, classified edges by destination color, found the boolean-visited bug, and applied the pattern to Course Schedule. Now construct the cycle detection code yourself.

There is something elegant about this algorithm that is worth appreciating before you build it. Most graph algorithms require you to maintain complex state -- distance maps, priority queues, predecessor arrays. Directed cycle detection requires exactly one array: a color for each node. Three possible values. Three transitions. And that is enough to correctly classify every edge in the graph, distinguish real cycles from harmless revisits, and handle arbitrarily complex DAG structures that would fool a boolean approach.

The simplicity is also what makes it easy to get subtly wrong. The most common mistake is not the boolean-visited trap (you already caught that one). It is forgetting the white-to-black transition -- entering the node, exploring neighbors, but never marking it black on the way out. That leaves the node gray forever, which means any future encounter with it looks like a back edge. On graphs with convergent paths (where multiple branches lead to the same node), this bug produces false positives that look identical to the boolean-visited bug. The fix is the same: ensure every node that enters the gray state eventually exits it.

Three blanks, one for each color transition in the DFS lifecycle. The first blank: what happens when DFS enters a node? Mark it gray. The second blank: what do you check for each neighbor? If the neighbor is gray, you have found a back edge -- a cycle. The third blank: what happens when DFS leaves a node (all neighbors explored, about to return)? Mark it black.

These three transitions -- white-to-gray on entry, gray check on neighbors, gray-to-black on exit -- are the entire algorithm. If you can write them without hesitation, you own directed cycle detection.

Four questions that test whether you own the three-color model or just memorized it.

Here is why this matters beyond the algorithm itself. Cycle detection on directed graphs is a gateway to topological sorting. If a directed graph has no cycles (it is a DAG), then the nodes can be arranged in a linear order where every edge points forward -- a topological order. Topological sort is just DFS with one extra line: when a node turns black (fully processed), prepend it to the result list. The three-color DFS you just built is one line away from topological sort, which is one line away from solving Course Schedule II (LC 210), Alien Dictionary (LC 269), and dozens of dependency-ordering problems.

The reason the three-color model is worth internalizing deeply -- not just memorizing -- is that it is the foundation of this entire family of algorithms. If you understand why gray-to-gray means cycle and gray-to-black means safe, you can reconstruct the cycle detection, topological sort, and strongly connected component algorithms from first principles.

You will need to reason about why boolean visited fails on directed graphs, when a gray neighbor signals a cycle versus when a black neighbor is safe, how the parent-tracking trick works for undirected graphs, and how to apply the pattern to a scheduling problem you have not seen before. The key distinction: gray means “in progress -- I am your ancestor, and you are about to close a loop.” Black means “finished -- seeing me again is harmless.”