How do you detect a cycle in a directed graph?

Use DFS with three-state coloring: white for unvisited, gray for currently in the recursion stack, and black for fully processed. Start DFS from each unvisited node, marking it gray. If during exploration you encounter a gray node, a cycle exists because you have found a back edge to an ancestor in the current path. When a node's DFS completes with no cycle found, mark it black. Black nodes are safe to skip entirely. This runs in O of V plus E time. The gray state distinguishes back edges that indicate cycles from cross edges to already-processed nodes that do not indicate cycles. ---