Course Schedule

Problem (restated)

n courses with prereq pairs [a,b] meaning b before a. Return whether you can finish all.

Intuition

Detect cycle in directed graph via topo sort; if order length < n, cycle.

Approaches

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  while (q.length) {
    const u = q.shift()!;
    taken++;
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return taken === numCourses;
}

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  while (q.length) {
    const u = q.shift()!;
    taken++;
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return taken === numCourses;
}

Template connection

Topological sort cycle detect.

Reflection

• The edge runs from prerequisite to course. Kahn puts indegree 0 on the queue. If fewer than n nodes leave the queue, there is a cycle and the answer is false.
• [[0,1],[1,0]] is a cycle. No edges is true. Counting the same prerequisite twice inflates the indegree.
• A colored DFS that returns to a gray node is the same cycle. Both methods agree.