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
            for(auto req : prerequisites)
                //collect all limited courses by req.second
                //number of courses needed to be finished before 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
                //take one course
                //int course = sq.front(); //for queue
                int course = sq.top();
                //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.