210. Course Schedule II

There are numCourses courses and prerequisites[i] = [a, b] means b must be taken before a. Return an order in which all courses can be taken, or [] if that is impossible.

A course finishes in DFS only after everything that depends on it has finished. Reversing the finish order gives a valid schedule; reaching a node still on the path means a cycle.

1function findOrder(numCourses: number, prerequisites: number[][]): number[] {
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), post: number[] = [];
5  const dfs = (u: number): boolean => {
6    if (state[u] === 1) return false;
7    if (state[u] === 2) return true;
8    state[u] = 1;
9    for (const v of adj[u]) if (!dfs(v)) return false;
10    state[u] = 2; post.push(u);
11    return true;
12  };
13  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return [];
14  return post.reverse();
15}

courses (prereq → course)

finish order = []

Build the adjacency list.

1 / 0

Space: play/pause · ←/→: step