So far, every graph you've processed has had a valid topological ordering. Kahn's algorithm processed every node. DFS colored every node BLACK. The queue never starved. The recursion never got confused.

That's about to change.

What happens when you run a topological sort algorithm on a graph that ISN'T a DAG? You proved in Module A that cycles make ordering impossible. But you've never seen what that looks like from the algorithm's perspective. You've never watched Kahn's try and fail, or DFS encounter something it shouldn't.

Cycles in real systems don't announce themselves. A circular dependency in a build system looks like any other dependency until make stalls. A deadlock in a task scheduler looks fine until the queue drains and three processes sit there, each waiting for the one before it. A database migration that references a table it's supposed to create — you don't notice until the migration tool hangs.

The question isn't “how do I check for cycles” — it's “do the algorithms I already know detect them automatically?” The answer is one of the most elegant properties in all of graph theory: topological sort algorithms don't just sort. They detect cycles as a free byproduct. You've been running a cycle detector this whole time without knowing it.

Here's an 8-node graph. It looks normal — edges, dependencies, the usual. Run Kahn's algorithm on it. Process the ready nodes. Watch the queue.

At some point, something will go wrong. Your job: figure out what happened, and why.

The queue starved. It ran out of ready nodes while unprocessed nodes remained — nodes whose in-degrees refused to drop to zero because they were waiting on each other in a loop. Nobody in the cycle could go first, so nobody entered the queue, so the algorithm halted early.

This is cycle detection by absence. The algorithm doesn't look for cycles. It simply notices that result.length < n when it finishes — fewer nodes were processed than exist in the graph. The missing nodes are exactly the ones trapped in cycles. You don't need a separate cycle-checking pass. The sort IS the check.

In practice, this means the one-line addition if (result.length < n) return "CYCLE" after the main loop transforms Kahn's algorithm from a topological sorter into a cycle detector — with zero additional time complexity. The information was there all along; you just needed to notice the gap between what was processed and what exists.

Same graph. Different algorithm. DFS with three-color marking: WHITE (unvisited), GRAY (in progress, on the call stack), BLACK (finished). Watch the colors change as DFS descends into the graph.

Pay close attention to the moment when DFS tries to visit a node that's already GRAY. That node is on the current call stack — it's an ancestor of the node doing the visiting. What does it mean when a descendant has an edge pointing back to its own ancestor?

A back edge. An edge from a descendant to its own ancestor on the current DFS path. The three-color system makes the detection instant: GRAY means “I'm still on the call stack, my subtree isn't finished.” When you encounter a neighbor that's GRAY, you've found a path from that neighbor down to you (through the tree) AND an edge from you back to that neighbor (the back edge). That's a cycle.

The key distinction from Kahn's: DFS catches cycles the moment a back edge appears. It doesn't need to wait until the algorithm finishes. The call stack from the GRAY node to the current node IS the cycle. You have the exact cycle path immediately, not just “some nodes are stuck.”

In code, it's a single check inside the DFS loop: if (color[neighbor] === GRAY) return "CYCLE". Everything else about the DFS traversal stays the same. The cycle detection is free — it's a byproduct of the three-color invariant you're already maintaining.

You've now seen both algorithms fail on the same graph. Kahn's fails by starvation: the queue empties before all nodes are processed. DFS fails by back-edge: it encounters a gray node that's already on the current call stack. Same cycle. Different detection mechanisms. Neither requires a separate “cycle check” — detection is a free byproduct of the algorithm itself.

This is one of the most elegant properties of topological sort algorithms. You don't run the sort and then run a separate cycle detector. The sort IS the detector. Kahn's tells you “these nodes are trapped” (any node not in the output is part of or downstream of a cycle). DFS tells you “here's the exact cycle” (the back-edge gives you the cycle path immediately).

In practice, this means your cycle detection code is your topological sort code with one extra check:

For Kahn's: return result.length === n ? result : "CYCLE". If the output is too short, there's a cycle. The remaining nodes are the evidence.

For DFS: if (color[neighbor] === GRAY) return "CYCLE". If you encounter a gray node during DFS, there's a back-edge. The call stack from the gray node to the current node is the cycle.

Both run in O(V + E). Both give you the topo ordering when no cycle exists and the cycle evidence when one does. The choice between them comes down to what else you need: Kahn's if you want queue-based processing order, DFS if you're already doing a depth-first traversal.

Here's an honest admission: the first time I encountered a cycle in production code — a circular dependency between three microservices — I wrote a separate cycle-detection algorithm. I didn't realize the topological sort I was already using for build ordering would have caught it. That was a week of unnecessary work. The sort and the detector are the same algorithm.

You've seen both detection mechanisms in action. Kahn's starvation told you nodes were trapped. DFS back-edge told you exactly where the cycle was. But seeing and writing are different things.

Fill in the blanks to turn both algorithms into cycle detectors. Each blank maps to a specific moment you already experienced: the starvation check from Kahn's Autopsy, and the GRAY neighbor check from the three-color DFS.

Here's a clean 6-node DAG. No cycles. Every edge points forward. Your job: add exactly ONE edge that creates a cycle. But before you place it, you must predict how many nodes Kahn's will process before stalling.

This isn't just about finding a backward edge — it's about understanding the consequences. Which nodes will be trapped? How far will Kahn's get before the queue drains? The prediction forces you to trace the structural impact of your edit.

Every cycle-creating edge points “backward” in the topological order — from a node that comes later to one that comes earlier. That's the definition: if you can reach node X from node Y through the existing edges, then adding Y⟶X closes the loop. The hard part isn't knowing this rule — it's predicting which nodes get caught in the blast radius. Some backward edges trap 2 nodes. Others trap 5. The stall depth depends on how many nodes are downstream of the cycle.

Three tasks: diagnose a starvation, identify a back-edge, and fill in the detection code. All construction.