题解 | #检测循环依赖#

拓扑排序的简单运用。

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
        map<int,vector<int> > mp;  // a->b
        vector<int> ans;
        int indegree[2001] = {0};
        //memset(indegree,0,sizeof(indegree));
        queue<int> qu;
        for(int i = 0;i < prerequisites.size();++i){
            mp[prerequisites[i][1]].push_back(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        for(int i = 0;i < n;++i){
            if(indegree[i] == 0)
                qu.push(i);
        }
        while(!qu.empty()){
            int start = qu.front();
            ans.push_back(start);
            qu.pop();
            for(int i = 0;i < mp[start].size();++i){
                indegree[mp[start][0]]--;
                if(indegree[mp[start][0]] == 0)
                    qu.push(mp[start][0]);
            }
        }
        if(ans.size() != n)
           ans.clear();
        return ans;
    }
};