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> requires_count(n, 0);
        vector<vector<int>> enable_courses(n, vector<int>{});
        for (const auto &p : prerequisites) {
            enable_courses[p[1]].push_back(p[0]);
            ++requires_count[p[0]];
        }

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

        int finished_count = 0;
        while (!courses.empty()) {
            int course = courses.front();
            courses.pop();
            ++finished_count;

            for (int e : enable_courses[course]) {
                --requires_count[e];
                if (requires_count[e] == 0) {
                    courses.push(e);
                }
            }
        }

        return finished_count == n;
    }
};