LeetCode 207 · Topological Sort · BFS

Course Schedule

MediumDecide if all courses can be finished — i.e. the prereq graph has no cycle.
There are numCourses courses labeled 0..numCourses-1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, otherwise false.

Walkthrough

try:
[a, b] means “take b before a”. Arrow points prereq → course.
1
function canFinish(numCourses, prerequisites) {
2
  const adj = Array.from({length: numCourses}, () => []);
◄
3
  const indeg = new Array(numCourses).fill(0);
4
  for (const [a, b] of prerequisites) {
5
    adj[b].push(a);   // b is a prerequisite of a
6
    indeg[a]++;
7
  }
8
  const queue = [];
9
  for (let c = 0; c < numCourses; c++)
10
    if (indeg[c] === 0) queue.push(c);
11
  let taken = 0;
12
  while (queue.length) {
13
    const u = queue.shift();
14
    taken++;
15
    for (const v of adj[u]) {
16
      indeg[v]--;
17
      if (indeg[v] === 0) queue.push(v);
18
    }
19
  }
20
  return taken === numCourses;
21
}
numCourses = 2
0010
ready (indeg 0)takingtakennindegree
queue (ready courses)
(empty)
STEP 0 / 20 · line 2
Set up the bookkeeping
adj[c] will list the courses that depend on c. indeg[c] counts how many prerequisites course c still needs. Everything starts empty / zero.

Intuition

Treat each course as a node and each prerequisite [a, b] as an arrow b → a (“take b before a”). You can finish everything exactly when these arrows contain no cycle.

For each course, count how many prerequisites it still needs — its indegree. A course with indegree 0 has nothing blocking it, so it can be taken right now.

Take any ready course and “complete” it: that removes one prerequisite from every course that depended on it. Some of those may drop to indegree 0 and become ready themselves.

Keep taking ready courses. If you take all of them, there was no cycle → true. If you get stuck with courses whose indegree never reaches 0, they depend on each other in a cycle → false.

The algorithm

  1. 01Build the graph: for each [a, b] add edge b → a and increment indegree[a].
  2. 02Put every course with indegree 0 into a queue.
  3. 03Pop a course, count it as taken, and decrement the indegree of each course it points to; if any reaches 0, enqueue it.
  4. 04Repeat until the queue is empty.
  5. 05Return true if the number taken equals numCourses (otherwise a cycle blocked some).

Reference implementation

1
function canFinish(numCourses, prerequisites) {
2
  const adj = Array.from({ length: numCourses }, () => []);
3
  const indeg = new Array(numCourses).fill(0);
4
  for (const [a, b] of prerequisites) {
5
    adj[b].push(a);    // b is a prerequisite of a
6
    indeg[a]++;
7
  }
8
  const queue = [];
9
  for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
10
  let taken = 0;
11
  while (queue.length) {
12
    const u = queue.shift();
13
    taken++;
14
    for (const v of adj[u]) {
15
      indeg[v]--;
16
      if (indeg[v] === 0) queue.push(v);
17
    }
18
  }
19
  return taken === numCourses;
20
}

Complexity

Time
O(V + E) — each course and prerequisite is processed once.
Space
O(V + E) for the adjacency list, indegree array, and queue.