DFS 3-color

boolean hasCycle(List[] graph) {
  int[] color = new int[graph.length]; // 0=WHITE, 1=GRAY, 2=BLACK
  for (int i = 0; i < graph.length; i++)
    if (color[i] == 0 && dfs(i, graph, color)) return true;
  return false;
}
boolean dfs(int u, List[] graph, int[] color) {
  color[u] = 1;
  for (int v : graph[u]) {
    if (color[v] == 1) return true;
    if (color[v] == 0 && dfs(v, graph, color)) return true;
  }
  color[u] = 2;
  return false;
}
Advertisement

Kahn&amp;#x27;s / topological

Repeatedly remove sources (in-degree 0). If not all vertices removed → cycle. Also O(V+E).

Advertisement

Finding a cycle

When back edge (u,v) found, trace parents from u back to v to extract cycle vertices.

Applications

Deadlock detection. Course prerequisite validation. Build system dependency check.