课程表 II

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);
        vector<int> inDegree(numCourses);

        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
            inDegree[info[0]]++;
        }

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

        vector<int> res;
        while (!q.empty()) {
            int current = q.front();
            q.pop();

            res.push_back(current);
            for (int v : edges[current]) {
                if (--inDegree[v] == 0)
                    q.push(v);
            }
        }

        if (res.size() < numCourses) return {};
        return res;
    }
};