28ms C++ concise solution with explanation


  • 0
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> graph(numCourses);
            vector<int> preNum(numCourses), res;
            stack<int> sq; //DFS
            //queue<int> sq; //BFS
    
            //preprocessing
            for(auto req : prerequisites)
            {
                //collect all limited courses by req.second
                graph[req.second].push_back(req.first);
                //number of courses needed to be finished before req.first
                preNum[req.first]++;
            }
    
            //put avaliable courses in the stack
            for(int i=0; i<numCourses; ++i)
            {
                if(preNum[i]==0) sq.push(i); //avaliable to take
            }
    
            //start to take course one by one
            while(!sq.empty())
            {
                //take one course
                //int course = sq.front(); //for queue
                int course = sq.top();
                sq.pop();                   
                res.push_back(course);
                //released courses after taking the course                 
                for(auto c : graph[course])
                {
                    //no prerequist, avaliable to take
                    if(--preNum[c]==0) sq.push(c); 
                }
            }
            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.