Description

Submission

class Solution {

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        int n = numCourses;
        unordered_map<int, vector<int>> nextCourse;
        unordered_map<int, int> degree;

        for(auto p: prerequisites) {
            nextCourse[p[1]].push_back(p[0]);
            degree[p[0]]++;
        }

        vector<int> rets;

        queue<int> q;
        for(int i = 0; i < n; ++i) {
            if(degree[i] == 0) q.push(i);
        }

        while(!q.empty()) {
            for(int course : nextCourse[q.front()]) {
                degree[course] -= 1;
                if(degree[course] == 0) q.push(course);
            }
            rets.push_back(q.front());
            q.pop();
        }

        if(rets.size() != n) return {};
        return rets;
    }
};