1、思路

• 只有有向无环图才存在拓扑排序。每次寻找图中入度为0的节点，将其删除后再找下一批入度为0的节点，这样的顺序叫做拓扑序；

• 计算每门课的入度，找出所有入度为0的课程将它们放入队列中；

• 每个循环删除一个入度为0的课程，并将对应的后置课程的入度减1，若其中有入度变为0的后置课程，继续把它加入到队列中。

2、代码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> hash;
        vector<int> inDegrees(numCourses, 0);                   //保存每门课的入度

        for (vector<int>& prerequisite : prerequisites)
        {
            hash[prerequisite[1]].push_back(prerequisite[0]);   //记录当前课程的后置课程
            inDegrees[prerequisite[0]] ++ ;                     //记录入度
        }

        queue<int> q;
        //将入度为 0 的课程放入队列，若不存在，则表示每门课程都互相依赖，不可能完成所有课程
        for (int i = 0; i < numCourses; ++ i)
        {
            if (inDegrees[i] == 0)
            {
                q.push(i);
            }
        }

        vector<int> res;
        //注意：只有入度为 0 的课程才能放入队列 q 中
        while (!q.empty())
        {
            int course = q.front();
            q.pop();
            res.push_back(course);          //将当前课程放入可行的修课序列

            for (int next : hash[course])   //遍历当前课程的后置课程
            {
                inDegrees[next] -- ;        //所有对应的后置课程入度减 1

                if (inDegrees[next] == 0)   
                {
                    q.push(next);
                }
            }
        }

        //检查是否每一门课程都能修完，否则返回空数组
        if (res.size() == numCourses) return res;
        return {};
    }
};