课程表

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [\(a_i\), \(b_i\)] indicates that you must take course \(b_i\) first if you want to take course \(a_i\).

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0], [0,1]]

Output: false

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= \(a_i\), \(b_i\) < numCourses
• All the pairs prerequisites[i] are unique.

Idea

Model the courses as a directed graph with an edge \(b_i \to a_i\) for each prerequisite. All courses can be finished if and only if the graph has no cycle, which we can check with a topological sort using Kahn's algorithm (BFS).

Count the in-degree of every course and push all courses with in-degree 0 into a queue. Repeatedly pop a course, count it as taken, and decrease the in-degree of its neighbors; any neighbor whose in-degree drops to 0 is pushed into the queue.

If the number of taken courses equals numCourses, return true. Otherwise some courses are stuck in a cycle, so return false.

Time complexity: \(O(V + E)\), Space complexity: \(O(V + E)\), where \(V\) is numCourses and \(E\) is the number of prerequisites

Pseudo Code

graph = array of numCourses empty lists;
indegree = array of numCourses zeros;
for ([a, b] in prerequisites) {
    graph[b].add(a);
    indegree[a]++;
}

queue = empty queue;
for (i = 0; i < numCourses; i++) {
    if (indegree[i] == 0) {
        queue.push(i);
    }
}

taken = 0;
while (!queue.isEmpty()) {
    course = queue.pop();
    taken++;
    for (next in graph[course]) {
        indegree[next]--;
        if (indegree[next] == 0) {
            queue.push(next);
        }
    }
}

return taken == numCourses;