STEP 15 · GRAPHS · GRAY MEANS STILL ON MY PATH · MEDIUM

Detect Cycle in a Directed Graph

WHAT IT SAYS

Determine whether a directed graph contains a cycle.

WHAT IT'S REALLY ASKING

"The undirected trick — 'visited node that isn't my parent' — lies here: in a directed graph you can legally re-meet a node from a FINISHED exploration (two roads into the same city, no loop anywhere). The question directedness forces is sharper: is this visited node still ON MY CURRENT PATH? Only an edge back into your own unfinished ancestry closes a loop. Visited needs three states, not two."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Port the undirected detector

O(V + E) time — and WRONG on the most basic diamond

Run DFS with a boolean visited array; report a cycle whenever a neighbour is already visited (with or without the parent exemption carried over from the undirected version).

WHERE THE WORK IS WASTED — Not waste — a false conviction. Take edges A→B, A→C, B→D, C→D: no cycle (nothing returns anywhere), but DFS finishing the B-branch marks D visited, then the C-branch meets D and the boolean detector cries cycle. The failure is conceptual: 'visited' conflates two situations that directedness pulls apart. Meeting a node whose exploration is COMPLETE means converging roads — every path onward from it was already exhausted without returning to you, so no loop is possible through it. Meeting a node whose exploration is STILL OPEN — an ancestor on your current stack — means your path has come back to bite its own tail. One bit cannot distinguish 'done' from 'in progress', and the distinction is the entire problem.

KEY OBSERVATION — THE UNLOCKlink

A cycle is an edge into your own open ancestry.

Give every vertex one of three states: WHITE (untouched), GRAY (DFS has entered but not yet finished it — it sits on the current recursion stack, an open ancestor), BLACK (entered and fully finished — every path out of it exhausted). The claim: a directed graph has a cycle if and only if DFS ever finds an edge pointing at a GRAY vertex. Forward direction: an edge u→v with v gray means v is an ancestor of u on the current DFS path — the tree path v ⇝ u exists, and the edge u→v closes it into a directed cycle, exhibited on the spot. Backward direction: suppose a cycle exists and let v be the FIRST of its vertices that DFS enters. While v is gray, DFS explores everything reachable from v — which includes the rest of the cycle — so it reaches the cycle's edge pointing back at v while v is still gray. The back edge cannot be missed. Meanwhile black vertices are provably safe to re-meet: when a vertex turns black, everything reachable from it has been searched and no gray ancestor was hit, so no path through it returns to the current stack — the diamond's second arrival at D bounces off harmlessly. Bookkeeping in practice: a recStack boolean set on entry and CLEARED ON EXIT alongside the permanent visited flag — the clearing is the step the broken version lacked, and forgetting it silently degrades three states back to two. Sweep all vertices, launching DFS from each white one; cycles hide in any component. The dual worth knowing because it inverts the perspective: Kahn's algorithm repeatedly removes vertices of in-degree zero (nothing left pointing at them). A DAG always offers such a vertex (follow edges backward — finiteness forces a source unless you loop), so removal consumes everything; a cycle's vertices all wait on each other, in-degrees never reaching zero, and the process stalls with vertices remaining. Cycle ⟺ removal count < V. DFS finds the cycle by walking INTO it; Kahn detects it as the residue that peeling cannot touch — the same theorem ('cycle ⟺ no topological order') proved from both ends, and Kahn hands you the topological order for free when the answer is no-cycle.

DFS with recStack, or Kahn's peeling

O(V + E) time either way; O(V) for the state arrays or the in-degree queue

DFS: visited[] and recStack[]; on entry set both, recurse into neighbours — gray (recStack true) neighbour returns cycle, white recurses, black skips — on exit clear recStack. Launch from every white vertex. Kahn: compute in-degrees, queue the zeros, repeatedly pop-and-decrement-neighbours, enqueueing new zeros; processed < V means cycle.

WHAT YOU TRADED — DFS exhibits the actual cycle (the gray vertex plus the current stack IS the loop) but risks recursion depth on long chains; Kahn is iterative and produces the topological order as a byproduct, but on failure names only the leftover vertex SET, not a specific cycle. Choose by deliverable. The transferable lesson: directedness splits 'visited' into in-progress versus finished, and only the in-progress kind convicts — the three-colour discipline is the foundation under topological sort, deadlock detection, and safe-state search (Course Schedule, Eventual Safe States) alike.

WATCH THE IDEA RUN

THE OPEN PATH — every GRAY node is here

stack empty — every branch explored

white / GRAY / black unseen / on my path / done

verdict no cycle yet

The undirected trick — 'visited and not my parent' — collapses here. In a directed graph you can legitimately reach an already-visited node from a totally separate branch, and that is not a cycle at all. Two states cannot tell the two situations apart.

step 1 / 7

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Three Colours: Only Gray Convicts

YOU'LL SEE IT AGAIN WHEN

The graph is DIRECTED — re-meeting a finished vertex is legal convergence, so the undirected visited-means-cycle logic false-positives on diamonds.
A cycle is precisely an edge into the CURRENT recursion stack — state must distinguish open ancestry (gray) from completed exploration (black).
Topological order is wanted, or detection should be iterative/incremental — Kahn's peeling gives cycle-detection and the ordering in one pass.

SAME BLUEPRINT, DIFFERENT PROBLEM

Detect Cycle in an Undirected Graph (why two states sufficed there)Course Schedule / Course Schedule II (this problem wearing a syllabus)Find Eventual Safe States (black = safe, formalised)Topological Sort

The bar isn't "solved it once." It's "could rebuild it from the observation."