8.2 Cycle Detection (Directed)

Demo: Course Schedule — LC 207 (Medium — Google/Amazon High)

Statement (Demo): There are numCourses courses and prerequisites[i] = [a, b] means course b must come before a. Return whether every course can be finished. Example: numCourses=2, prerequisites=[[1,0]] → true; numCourses=2, prerequisites=[[1,0],[0,1]] → false (cycle) | ⚡ numCourses ≤ 2000

Approach: Keep a state per node during DFS — 1 means "on the current recursion path". Reaching a state-1 node again means a cycle. A state-2 (fully done) node is safe to skip.

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const state = new Array(numCourses).fill(0); // 0=new, 1=visiting, 2=done
  const hasCycle = (u) => {
    if (state[u] === 1) return true;
    if (state[u] === 2) return false;
    state[u] = 1;
    for (const v of adj[u]) if (hasCycle(v)) return true;
    state[u] = 2;
    return false;
  };
  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
  return true;
}

Complexity: Time O(V + E), Space O(V + E)