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&#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.