Topological Sort

Cycle Detection (Directed)

Use three states per node: unvisited, in-progress, completed. If DFS visits an 'in-progress' node, you've found a back edge → cycle. A node moves to 'completed' only after all descendants are fully processed.

O(V + E)

O(V)

say this out loud

In a directed graph I need three states, not two. A node currently on the recursion stack means a back edge and therefore a cycle.

How It Works

Cycle detection in a directed graph uses three node states: white (unvisited), gray (in progress, currently on the DFS recursion stack), and black (completely finished). DFS colors a node gray on entry and black only after all its descendants finish. If the traversal ever steps into a gray node, it has found a back edge (an edge pointing to an ancestor still on the stack) which is exactly a directed cycle.

The distinction between gray and black is the whole trick: reaching a black node is harmless (that subgraph is fully explored and cycle-free), while reaching a gray node closes a loop. A single visited boolean cannot tell these apart and produces false positives on diamond-shaped DAGs. The check runs in O(V + E), and starting DFS from every white node covers disconnected regions.

Step-by-Step Visualization

Directed edges 0 to 1, 1 to 2, 2 to 0, and 2 to 3. White is unvisited, grey is on the current call stack, black is finished

stateall white

1/7

Code

Java

static boolean hasCycle(List<List<Integer>> graph) {
  int[] state = new int[graph.size()]; // 0=white, 1=gray, 2=black

  for (int i = 0; i < graph.size(); i++)
    if (state[i] == 0 && dfs(graph, i, state)) return true;
  return false;
}

static boolean dfs(List<List<Integer>> graph, int node, int[] state) {
  state[node] = 1; // Gray
  for (int nei : graph.get(node)) {
    if (state[nei] == 1) return true;  // Cycle!
    if (state[nei] == 0 && dfs(graph, nei, state)) return true;
  }
  state[node] = 2; // Black
  return false;
}

Tips & Gotchas

1Use 3 states: WHITE (unvisited), GRAY (in progress), BLACK (done)

2If DFS visits a GRAY node, we found a back edge → cycle!

3Works for directed graphs. For undirected, just check parent

Practice Problems

1Course Schedule
2Find Eventual Safe States
3Detect Cycles in 2D Grid

About the Topological Sort Pattern

Order the nodes of a directed graph so that for every edge A→B, A comes before B. Only works on DAGs (directed acyclic graphs). If a cycle exists, topological sort is impossible, which is how you detect cycles.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Why do I need three states instead of a simple visited set?

Two nodes can both point to a shared successor in a DAG, so revisiting a finished node is normal and not a cycle. Only revisiting a node that is still on the current recursion path proves a cycle. The gray state encodes 'on the current path', which a single boolean cannot.

How does directed cycle detection differ from the undirected case?

In an undirected graph you only need to check that a visited neighbor is not your direct parent, because edges are symmetric. Directed graphs need the recursion-stack (gray) test, since an edge to any previously visited node might be a legitimate cross edge rather than a cycle.

Can I detect directed cycles without DFS?

Yes. Run Kahn's algorithm and count how many nodes reach in-degree zero. If fewer than V nodes are processed, the leftovers form or feed cycles. This BFS-style approach avoids recursion entirely.