1. Three colors
0 unvisited, 1 on the current path (visiting), 2 fully done.
const state = new Array(n).fill(0)Typorithm · medium
Cycle Detection
▷ Interactive algorithm labcycle-detectiongraph-algorithmsthree-colorrecursion-stackdirected
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Cycle Detection
Graph Algorithms
DFS with three colors: a back edge to a node still on the recursion path proves a directed cycle.
In a directed graph a cycle exists when DFS finds an edge to a node it is still exploring.
Three states distinguish a node on the current path (1) from one already finished (2).
An edge to a state-1 node is a back edge and signals a cycle; state-2 nodes are safe.
Preparing algorithm lab…
01
0 = unseen, 1 = on path, 2 = done.
02
Edge to a state-1 node = cycle.
03
Set state 2 after exploring.
function hasCycle(graph, n) {
const state = new Array(n).fill(0);
function dfs(node) {
state[node] = 1;
for (const next of graph[node]) {
if (state[next] === 1) return true;
if (state[next] === 0 && dfs(next)) return true;
}
state[node] = 2;
return false;
}
for (let node = 0; node < n; node += 1) {
if (state[node] === 0 && dfs(node)) return true;
}
return false;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Mark visiting
A node is on the active recursion path while its subtree is explored.
state[node] = 13. Back edge found
Reaching a node still in state 1 means an edge points back into the current path.
if (state[next] === 1) return true4. Explore unseen
Only recurse into untouched nodes and propagate any cycle found.
if (state[next] === 0 && dfs(next)) return true5. Mark done
Once fully explored, a node can never be part of a new back edge.
state[node] = 2A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.