iteration solution, c++ , beat 98%


  • 0
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> inDegree(numCourses,0);
            vector<vector<int>> pre(numCourses,vector<int>());
            for(auto p:prerequisites){
                pre[p.second].push_back(p.first);
                inDegree[p.first]++;
            }
            queue<int> que;
            vector<int> res;
            for(int i=0;i<inDegree.size();i++){
                if(inDegree[i]==0)
                    que.push(i);
            }
            while(!que.empty()){
                int tmp=que.front();
                que.pop();
                res.push_back(tmp);
                for(int next:pre[tmp]){
                    inDegree[next]--;
                    if(inDegree[next]==0){
                        que.push(next);
                    }
                }
            }
            if(res.size()==numCourses)
                return res;
            return {};
        }
    

Log in to reply
 

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