Not a very consice c++ version


  • 0
    P
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            if(prerequisites.empty()){
                vector<int> s(numCourses);
                iota(s.begin(), s.end(), 0);
                return s;
            }
            unordered_map<int, unordered_set<int> > graph;
            unordered_map<int, int> deg;
            for(auto& pre : prerequisites){
                if(!deg.count(pre.second))   deg[pre.second] = 0;
                if(!graph[pre.second].count(pre.first)){
                    graph[pre.second].insert(pre.first);
                    deg[pre.first]++;
                }
            }
            queue<int> buf;
            int tmp = 0;
            vector<int> res;
            for(auto& v : deg)  
                if(!v.second)   
                    buf.push(v.first);
            while(!buf.empty()){
                tmp = buf.front();
                res.push_back(tmp);
                buf.pop();
                for(auto& neigh : graph[tmp])
                    if(!--deg[neigh])
                        buf.push(neigh);
            }
            vector<int> t;
            if(res.size() != deg.size())
                return t;
            
            if(res.size() < numCourses)
                for(int i = 0; i < numCourses; i++)
                    if(!deg.count(i))
                        res.push_back(i);
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.