207. Course Schedule

https://leetcode.com/problems/course-schedule/

Problem

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

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

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:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

• You may assume that there are no duplicate edges in the input prerequisites.

• 1 <= numCourses <= 10^5

Solution

class Solution {
public:
    bool canFinish(const int n, vector<vector<int>>& pre) {
        int indegree[n];
        memset(indegree, 0, sizeof(int) * n);
        vector<vector<int>> adj(n, vector<int>());
        for (const auto &edge: pre) {
            adj[edge[1]].emplace_back(edge[0]);
            ++indegree[edge[0]];
        }
        stack<int> nodes;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) nodes.push(i);
        }
        int finished = 0;
        while (!nodes.empty()) {
            const int current = nodes.top();
            nodes.pop();
            for (const int adj: adj[current]) {
                --indegree[adj];
                if (indegree[adj] == 0) nodes.push(adj);
            }
            ++finished;
        }
        return finished == n;
    }
    
   
};

• #topologicalsort

• #graph