207. Course Schedule

1. Description

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.

2. Example

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.

3. 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.

4. Solutions

Breadth-First Search

m is the number of nodes, n is the number of edges
Time complexity: O(m + n)
Space complexity: O(m + n)

class Solution {
public:
    bool canFinish(int n, const vector<vector<int>> &prerequisites) {
        vector<int> required_courses(n, 0);
        vector<vector<int>> enabled_courses(n);
        for (const auto &p : prerequisites) {
            ++required_courses[p[0]];
            enabled_courses[p[1]].push_back(p[0]);
        }

        queue<int> available;
        for (int i = 0; i < n; ++i) {
            if (required_courses[i] == 0) {
                available.push(i);
            }
        }

        int finished = 0;
        while (!available.empty()) {
            int course = available.front();
            available.pop();

            ++finished;

            for (int c : enabled_courses[course]) {
                --required_courses[c];
                if (required_courses[c] == 0) {
                    available.push(c);
                }
            }
        }

        return finished == n;
    }
};