[recommend for beginners]clean C++ implementation with detailed explanation


  • 3

    JUST THE SAME AS THE previous question.
    We just can use extra vector-array to record the result.

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> result;
            vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
            for(int i=0; i<prerequisites.size(); i++)
                graph[prerequisites[i].second].insert(prerequisites[i].first);
            vector<int> in_degree(numCourses, 0);
            for(int i=0; i<graph.size(); i++)
                for(auto it:graph[i])
                    in_degree[it]++;
                    
            int count=0;
            for(int i=0; i<numCourses; i++){
                int j;
                for(j=0; j<numCourses; j++) if(in_degree[j]==0)  break;
                /*** return {} means return null vector ***/
                if(j==numCourses)   return {};
                in_degree[j]=-1;
                for(auto it : graph[j])   in_degree[it]--;
                result.push_back(j);
            }
            return result;
        }
    };

Log in to reply
 

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