Topological Sort

There are a total of n courses you have to take, labeled from 0 to n - 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?

For example:

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

2, [[1,0],[0,1]] 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.

使用拓扑排序的方法，(1)统计图中所有入度为0的节点，将所有与此节点连接的节点的入度减一,（2）将上述节点所有满足入度为0的节点加入到队列中，重复

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //不要用邻接矩阵，内存会超啊
        vector<set<int>> graph(numCourses);
        vector<int> degrees(numCourses, 0);

        for(auto it = prerequisites.begin(); it!= prerequisites.end(); it++){
        //注意此处有个去重的过程，否则一下测试用例通不过，如果不去重，会使9的入度统计多1，有两个[1, 9]
        /*10
[[5,8],[3,5],[1,9],[4,5],[0,2],[1,9],[7,8],[4,9]]*/
            if(graph[it->second].find(it->first) == graph[it->second].end()){
                graph[it->second].insert(it->first);
                degrees[it->first]++;
            }
        }

        queue<int> q;
        for(int i = 0; i < numCourses; i++){
            if(degrees[i] == 0){
                q.push(i);
            }
        }
        int count = 0;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            count++;
            for(auto i:graph[cur]){
                if(--degrees[i] == 0)
                    q.push(i);
            }
        }
        return count == numCourses;
    }
};

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<set<int>> graph(numCourses);
        vector<int> degrees(numCourses, 0);
        vector<int> res;

       for(auto it = prerequisites.begin(); it!= prerequisites.end(); it++){
            if(graph[it->second].find(it->first) == graph[it->second].end()){
                graph[it->second].insert(it->first);
                degrees[it->first]++;
            }
        }

        queue<int> q;
        for(int i = 0; i < numCourses; i++){
            if(degrees[i] == 0){
                q.push(i);
            }
        }
        int count = 0;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            count++;
            res.push_back(cur);
            for(auto i:graph[cur]){
                if(--degrees[i] == 0)
                    q.push(i);
            }
        }
        if(count == numCourses)
            return res;
        else
            return {};
    }
};