课程表 II

有向图的排序问题，统计每个课程的入度，优先选择入度为 0 的课程，然后逐步消除依赖，最终得到合法的学习顺序。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> in(numCourses, 0); // 入度数组
        vector<vector<int>> adj(numCourses); // 邻接表

        for (auto& p : prerequisites) {
            int course = p[0], pre = p[1];
            in[course]++; // 课程course的入度+1
            adj[pre].push_back(course); // 前置课程pre指向后续课程course
        }

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

        vector<int> result; 
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            result.push_back(curr); // 选择当前课程
            
            // 遍历当前课程的后续课程，减少入度
            for (int next : adj[curr]) {
                in[next]--;
                if (in[next] == 0) { // 后续课程的前置依赖已满足
                    q.push(next);
                }
            }
        }

        // 若结果集包含所有课程，返回顺序，否则返回空
        return result.size() == numCourses ? result : vector<int>();
    }
};