• 拓扑序：在图中从顶点u到顶点v有一条有向路径，则顶点u一定排在顶点v之前。满足这样的条件的顶点序列称为一个拓扑序。
    • 有向无环图：DAG - Directed Acyclic Graph
    • 入度：有向图的某个顶点作为终点的次数和。
    • 出度：有向图的某个顶点作为起点的次数和。
    1. class Solution {
    2. public:
    3.     vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    4.         unordered_map<int, vector<int>> mp; // 邻接表
    5.         vector<int> degree(numCourses, 0); // 入度
    6.         for (int i = 0; i < prerequisites.size(); i++) {
    7.             int u = prerequisites[i][1];
    8.             int v = prerequisites[i][0]; 
    9.             // u --> v
    10.             degree[v]++;
    11.             mp[u].push_back(v);
    12.         }
    13.         queue<int> que; // 入度为0的课程，加入队列
    14.         for (int i = 0; i < degree.size(); i++) {
    15.             if (degree[i] == 0) {
    16.                 que.push(i);
    17.             }
    18.         }
    19.         vector<int> ans;
    20.         int count = 0;
    21.         while (!que.empty()) {
    22.             int n = que.size();
    23.             for (int i = 0; i < n; i++) {
    24.                 int a = que.front();
    25.                 que.pop();
    26.                 ans.push_back(a);
    27.                 vector<int> tmp = mp[a];
    28.                 for (int j = 0; j < tmp.size(); j++) {
    29.                     degree[tmp[j]]--;
    30.                     if (degree[tmp[j]] == 0) {
    31.                         que.push(tmp[j]);
    32.                     }
    33.                 }
    34.                 count++;
    35.             }
    36.         }
    37.         if (count < numCourses) { // 有环，不可能完成所有课程
    38.             return {};
    39.         }
    41.         return ans;
    42.     }
    43. };

    若有些拓扑排序要求字典序最小，可将队列换成优先队列。
    priority_queue<int> que; // 大顶堆，降序