Course Schedule

Problem

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

The pair [0, 1], indicates that must take course 1 before taking course 0.

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.

Return true if it is possible to finish all courses, otherwise return false.

Examples

Example 1:

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

Output: true

Explanation: First take course 1 (no prerequisites) and then take course 0.

Example 2:

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

Output: false

Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.

Constraints

• 1 <= numCourses <= 1000
• 0 <= prerequisites.length <= 1000
• prerequisites[i].length == 2
• 0 <= a[i], b[i] < numCourses
• All prerequisite pairs are unique.

You should aim for a solution with O(V + E) time and O(V + E) space, where V is the number of courses (nodes) and E is the number of prerequisites (edges).

Solution

prerequisite[i] = [A,B] means that B -> A as an edge for B must be taken before A. We track the indegree for each node, and map the adjacency list for the edge directions. We start a queue with courses with no prerequisites. Every time we take a course, we decrement the counter for any course its a prerequisite for, and if that course now longer has blockers, we add to the queue.

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        std::vector<int> indegree(numCourses, 0);
        std::vector<std::vector<int>> adj(numCourses);
 
        // prerequisite[i] = [A,B]
        // B -> A  i.e. B is a prereq for A
        for (const auto &prerequisite : prerequisites) {
            ++indegree[prerequisite[0]];
            adj[prerequisite[1]].push_back(prerequisite[0]);
        }
 
        // Start off by taking courses with no prereqs
        std::queue<int> open;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                open.push(i);
            }
        }
 
        int courses_taken = 0;
        while (!open.empty()) {
            int course = open.front();
            open.pop();
            ++courses_taken;
            for (const auto &c : adj[course]) {
                --indegree[c];
                if (indegree[c] == 0) {
                    open.push(c);
                }
            }
        }
        return courses_taken == numCourses;
    }
};