图问题-207课程表

[liuyingbin19222]

输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

• 示例二： 输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
• idea: 判断是否形成环路，形成环路该课程表就不存在。可以使用拓扑排序实现遍历有向无环图；

• 课程表二： 输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3] 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。   因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

[liuyingbin19222]

课程表二解法： 使用拓扑排序输出顺序;

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> inDegree(numCourses,0); //   初始化将inDgree 矩阵每一个值为0；
        vector<vector<int>> adJust(numCourses,vector<int>()); //
        for(auto arr : prerequisites){
            inDegree[arr[0]]++;
            adJust[arr[1]].push_back( arr[0] );
        }
        queue<int> que;
        for(auto cnt = 0;cnt < inDegree.size();cnt++){
            if(inDegree[cnt] == 0) que.push( cnt );
        }
        vector<int> res;
        while(!que.empty()){
            auto tmp = que.front();
            que.pop();
            res.push_back(tmp);
            for(auto i : adJust[tmp]){
                if(--inDegree[i] == 0){
                    que.push(i);
                }
            }
        }
        if( res.size() == numCourses ) return res;
        else return {};
    }
};