概念及模板

有向圖的拓撲排序是指將有向無環圖中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u, v)在圖中，則u在該序列中排在v的前面。

例如，假設有n個任務，這些任務需要按照一定的順序執行，同時有些任務必須在其它任務完成之后才能執行，此時可以使用拓撲排序來確定任務的執行順序，從而保證所有任務都能夠被按照正確的順序執行完成。
比如：生成一個可執行程序，需要經歷預處理，編譯，匯編，鏈接四步，后面的步驟必須在前面的步驟完成后才能執行。

一個有向無環圖，一定至少存在一個入度為 0 的點（抽屜原理）
當有向圖中，某個點的入度為 0 的時候，說明是沒有一個點指向這個點的，那這個點就能作為起點指向其他點了，遍歷結束后，這個點就可以刪掉了（將 t 放在當前的最前面了），并將它指向的所有點的入度都減 1

1. 定義一個隊列，將所有入度為 0 的點入隊
2. 循環，每次取隊頭 t，枚舉 t 的所有出邊 j，將 d[j]-- ，如果減完后 d[j] == 0，就將這個點入隊，重復前面的操作，那么只要這個圖無環，就能依次將它的所有點突破掉

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int n, m；
int e[N], ne[N], h[N], idx;
int ret[N], p; // 記錄拓撲序的數組
int d[N]; // 記錄每個點的入度度數
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
int to_polo()
{queue<int> q;for(int i = 1; i <= n; i++) if(!d[i]) // 將所有入度為 0 的點全部入隊列 {q.push(i);ret[p++] = i;}while(q.size()){int t = q.front();q.pop();for(int i = h[t]; i != -1; i = ne[i]) // 遍歷所有出邊 {int j = e[i];d[j]--;if(d[j] == 0) // 如果等于 0, 就加入隊列 {q.push(j);ret[p++] = j;}}}if(p != n) return -1;else return 1;
}
int main()
{cin >> n >> m;memset(h, -1, sizeof h);while(m--){int a, b;cin >> a >> b;add(a, b);d[b] ++;}int ans = to_polo();if(ans == -1) cout << -1;else {for(int i = 0; i < p; i++) cout << ret[i] << " ";}return 0;
}

例題 雜務

雜務

題目中出現的，某一任務必須在某些任務完成后才能完成，這就是拓撲排序的標志

此題只需要記錄每個人物最快完成的時間即可：將所有入度為 0 的點放入隊列，然后遍歷所有出邊，將遍歷到的點的入度都減1，當一個點的入度減到 0 的時候，就可以加入隊列。
加入隊列后，這個點的最快時間就可以被更新了，最終答案在所有任務完成的最快時間中取最大值即可！

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10100;
const int M = 100100;
int n;
int e[M], ne[M], h[N], idx;
int ti[N]; // id -> time 每個點所需要的時間
int Com[N]; // 記錄每個點完成的最快時間 
int d[N]; // 記錄某個點的入度個數 
int ans; // 答案
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
void to_polo()
{queue<int> q;for (int i = 1; i <= n; i++){if (d[i] == 0){q.push(i);Com[i] = ti[i];ans = max(ans, Com[i]);}}while (q.size()){int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];Com[j] = max(Com[t], Com[j]); // 必須考慮最差情況d[j]--;if (!d[j]){Com[j] += ti[j];ans = max(ans, Com[j]);q.push(j);}}}cout << ans;
}
int main()
{memset(h, -1, sizeof h);cin >> n;for (int i = 1; i <= n; i++){int id, tim, tmp;cin >> id >> tim;ti[id] = tim;while (cin >> tmp){if (tmp == 0) break;add(tmp, id);d[id]++;}}to_polo();return 0;
}