210. Course Schedule II

這題跟選課1一樣, 差別在於你要紀錄修課的順序, 一旦有loop, 就返回空,

class Solution {
  public:
    vector<int> findOrder(int num, vector<vector<int>> &pre) {
        vector<int> indegree(num);
        vector<vector<int>> ncourse(num);
        vector<int> res;
        for (auto p : pre) {
            ncourse[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }
        queue<int> q;
        for (int i = 0; i < indegree.size(); i++) {
            if (indegree[i] == 0) {
                q.push(i);
                res.push_back(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (auto course : ncourse[cur]) {
                indegree[course]--;
                if (indegree[course] == 0) {
                    res.push_back(course);
                    q.push(course);
                }
            }
        }
        for (int i = 0; i < indegree.size(); i++) {
            if (indegree[i] != 0) {
                return {};
            }
        }
        return res;
    }
};