题解 | #检测循环依赖#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        vector<int> res;
        map<int,vector<int>>mp;
        int vis[n];
        queue<int> q;
        for(int i=0;i<prerequisites.size();i++){
            mp[prerequisites[i][1]]
            .push_back(prerequisites[i][0]);//[i][1]的下一个课程[i][0]是什么
            vis[prerequisites[i][0]]++;//前驱课程的门数
        }
        for(int i=0;i<n;i++){
            if(vis[i]==0){//前驱课程门数为0的直接加入队列（相当于没有约束）
                q.push(i);
            }
        }
        while(!q.empty()){
            int start=q.front();
            res.push_back(start);
            q.pop();
            //根据start当前位置所剩的课程数计算
            for(int i=0;i<mp[start].size();i++){
                vis[mp[start][0]]--;//mp[start][0]指向的课程, vis[mp[start][0]]其被指向的次数--
                if(vis[mp[start][0]]==0){//当前课程的前驱约束为0=没有约束
                    q.push(mp[start][0]);//进入队列
                }
            }
        }
        if(res.size()!=n){
            res.clear();
        }
        return res;
    }
};