207. Course Schedule

There are numCourses courses. prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses.

Mark nodes white (new), gray (on the current path) or black (done). Reaching a gray node means a back edge, which is a cycle.

1function canFinish(numCourses: number, prerequisites: number[][]): boolean {
2  const adj: number[][] = Array.from({ length: numCourses }, () => []);
3  for (const [a, b] of prerequisites) adj[b].push(a);
4  const state = new Array(numCourses).fill(0); // 0 white, 1 gray, 2 black
5  function hasCycle(u: number): boolean {
6    if (state[u] === 1) return true;
7    if (state[u] === 2) return false;
8    state[u] = 1;
9    for (const v of adj[u]) if (hasCycle(v)) return true;
10    state[u] = 2;
11    return false;
12  }
13  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
14  return true;
15}

courses (prereq → course)

state

white

Build the adjacency list.

1 / 0

Space: play/pause · ←/→: step