Concise and clear solution with two maps indegree and outdegree, no queue needed


  • 0
    X
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) 
        {
            map<int,set<int>> indeg,outdeg;
            set<int> courses;
            for(int i=0;i<numCourses;i++)
                courses.insert(i);
            for(auto req:prerequisites)
            {
                indeg[req.first].insert(req.second);
                outdeg[req.second].insert(req.first);
            }
            
            for(auto it:indeg)
                courses.erase(it.first);
            vector<int> res;
            while(courses.size())
            {
                int curr=*courses.begin();
                courses.erase(curr);
                res.push_back(curr);
                for(int next:outdeg[curr])
                {
                    indeg[next].erase(curr);
                    if(!indeg[next].size())
                        courses.insert(next);
                }
            }
            return res.size()==numCourses?res:vector<int>{};
        }
    };
    

Log in to reply
 

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