Graphs · Ordering · directed cycle detection LeetCode 207

Course Schedule / visualized

A node has three states, not two: white (never touched), grey (on the call stack right now), and black (fully explored, and proved clean). A grey → grey edge is a cycle; a grey → black edge is ordinary re-convergence. Collapse the two into one visited bit and the algorithm starts reporting cycles that are not there.

Adjacency — course i unlocks…, courses split by /

Marking

Execution

idle

Press Run to begin.

0 / 0

Speed

Java · running line

white — untouched grey — on the stack black — finished current node edge skipped

O(V + E) time, O(V) space · three colours because there are three facts, and the middle one is the only one the cycle test cares about. The verdict line is computed by Kahn’s algorithm — indegree-zero queue, emitted count against n — which shares no machinery with the DFS above, so it can disagree with it.