题解 | #体育课测验(二)#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
        // write code here
        vector<vector<int>> graph(numProject);
        vector<int> inDegree(numProject, 0);
        vector<int> order;

        // 构建图和计算入度
        for (auto& pre : groups) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        // 拓扑排序：使用队列
        queue<int> q;
        for (int i = 0; i < numProject; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            order.push_back(current);
            for (int adj : graph[current]) {
                inDegree[adj]--;
                if (inDegree[adj] == 0) {
                    q.push(adj);
                }
            }
        }

        // 检查是否所有节点都被处理
        if (order.size() != numProject) {
            return {};
        }

        return order;
    }
};