My c++ solution, using (unordered_map + queue)


  • 1
    G
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        unordered_map<int, unordered_set<int>> ins;
        for (auto& p : prerequisites) {
            ins[p.first].insert(p.second);
        }
        
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (ins.count(i) == 0) {
                q.push(i);
            }
        }
        
        vector<int> sol;
        
        while (!q.empty()) {
            int cur = q.front();
            sol.push_back(cur);
            q.pop();
            for (auto ii = ins.begin(), ie = ins.end(); ii != ie;) {
                ii->second.erase(cur);
                if (ii->second.size() == 0) {
                    q.push(ii->first);
                    ii = ins.erase(ii);
                } else {
                    ii++;
                }
            }
        }
        
        return sol.size() == numCourses ? sol : vector<int>();
    }

Log in to reply
 

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