在這個章節，我們要討論所謂的有向無環圖（Directed Acyclic Graph, DAG），也就是每條邊都有定向，而不存在一個環的圖。這種圖存在一種特殊的「順序」。
最好理解的例子應該就是遊戲裡面的「合成」了。假設你想要獲得某個物品（像是 Minecraft 裡面的木劍），你需要先拿到原料（木頭），然後根據這些原料合成一些中間物品（木板，木棍），最後再做出成品（木劍）。如果畫成一張圖的話，可能會長這樣：
假設我們知道這張圖，那要如何知道取得每一種物品用什麼順序呢？聰明的讀者可以一眼看出來，要先拿到木頭，把他換成木板，然後拿木板做成木棍，再合成木劍。那麼電腦要如何判斷這個順序呢？這就是「拓撲排序」演算法派上用場的時候。
為了解決上述的規劃問題，我們可以先將有向無環圖做「拓撲排序」，而答案就會是排序之後的順序做。這邊來看一個例題：
拓樸排序
給一張有向無環圖，所有點都是黑色，現在你需要把所有頂點塗白。不幸的，圖上所有的邊都是一條抹黑通道，只要被任何黑色點指向的點就無法塗白。你的任務是要輸出一個塗白的順序，使得所有頂點都有辦法被塗白。
要找出合理的排列順序的方法很像貪心法，首要目的就是得決定第一個被塗白的點！知道如何找出第一點，那麼就可以循序漸進的再找出第二點、第三點了。
可以作為第一點的點，想必它不必排在其他點後方塗色。也就是說，沒有被任何邊連向的點（也就是入度為 $0$ 的點），就可以作為第一點。如果有很多個入度為零的點，那麼找哪一點都行。
因為第一點已經被塗白，不會對整張圖造成任何影響了，因此我們可以將其拔掉（直接移出圖外），所有它指向別人的邊也再也沒有效用，所以可以一併拔掉。拔掉之後剩下的圖又是一張所有點都是黑色的有向無環圖了，而且與先前被拔掉的所有點無關！所以我們可以遞迴求解，找到第二、第三、……，一直到所有點都被找到為止。
實作上可以用一個 queue 來記錄所有入度是 $0$ 的點，每次都從 queue 的最前面取出一個點將其與它連出去的邊拔掉，萬一在拔掉的過程中有任何的頂點入度因此變成 $0$ 了，那就將入度歸零的點加進 queue 裡面。依照這個演算法做下去，最後拔點的順序就會是塗色的順序了！
int n = 頂點數;
vector<int> adj[MAX_N]; // adjacency lists
int inDegree[MAX_N]; // 記錄圖上每一個點目前的入度
void topological_sorting() {
// 累計圖上每一個點的入度
for (int i = 0; i < n; i++)
inDegree[i] = 0;
for (int i = 0; i < n; i++)
for (auto j : adj[i])
inDegree[j]++;
// 宣告一個queue來記錄已經沒有被任何邊連向的點
queue<int> que;
for (int i = 0; i < n; i++)
if (!inDegree[i])
que.push(i);
// 開始找出一個合理的排列順序
for (int i = 0; i < n; i++) {
// 尋找沒有被任何邊連向的點
if (que.empty())
break; // 找不到，目前殘存的圖是個環
int s = que.front();
que.pop();
inDegree[s] = -1; // 設為已找過（刪去s點）
cout << s << " "; // 印出合理的排列順序的第i點
// 更新inDegree的值（刪去由s點連出去的邊）
for (auto j : adj[s]) {
inDegree[j]--;
// 記錄已經沒有被任何邊連向的點
if (!inDegree[j])
que.push(j);
}
}
}
這個演算法在 $n$ 點 $m$ 邊的圖上，時間複雜度是多少呢？第 9 ~ 11 行會計算每個點的入度，因為每一條邊只被看一次，因此是 $O(n+m)$。在後面的迴圈中，注意到每個點只會有一個時刻入度變成 $0$，因此只會被加入到 queue 裡面一次。所以 30 ~ 35 行的迴圈對於每個點也只會進行一次，換句話說，每一條邊只會被看一次！所以整體的時間複雜度是 $O(n+m)$。
如果這張圖有環，那麼環上的點一定不會被放進 queue，因為他們都至少有一個入度。因此，有環的圖就不存在拓撲排序。
因為環上的點不會在 queue 中，queue 出現過的點數一定會小於這張圖的總點數。而這也是判斷一張圖是不是 DAG 的方法。
另外一種方法是使用 DFS 的方式。在從某個點 $u$ 做 DFS 時，我們會對 $u$ 所有指向的點 $v$ 遞迴。遍歷完所有 $u \rightarrow v$ 之後，某種程度上把 $u$ 所連出的邊都「拔掉」了。因此，我們可以做一個反向的拓撲排序：對於某個點 $u$，先遞迴處理所有 $u$ 指向的 $v$，然後將 $u$ 加到拓撲排序中。
int n = 頂點數;
vector<int> adj[MAX_N]; // adjacency lists
int vis[MAX_N];
vector<int> topological_order;
bool possible = 1;
void dfs(int u) {
vis[u] = 1;
for (int v : adj[u]) {
if (vis[v] == 0) {
dfs(v);
} else if (vis[v] == 1) { // 如果 v 尚未走完，而又有 u -> v, 那麼有環
possible = 0;
}
}
topological_order.push_back(u);
vis[u] = 2; // 將 u 設定為已經遍歷
}
void topological_sorting() {
possible = 1;
for (int i = 0;i < n;i++) {
if (vis[i] == 0) dfs(i);
}
reverse(topological_order.begin(), topological_order.end());
if (possible) {
for (int i:topological_order) cout << i << " ";
cout << "\n";
} else {
cout << "IMPOSSIBLE\n";
}
}
要如何知道一個問題能不能用拓撲排序呢？首先，我們要找出問題裡面，哪一些物件可以視為圖上的頂點。接下來，根據這些物件的相互依賴的關係畫出有向邊。最後，判斷這張圖是否能被拓撲排序的條件是否與題目所需的條件吻合。
以開頭的「遊戲合成」例子來說，每個物品就是一個點。如果物品 $Y$ 需要物品 $X$ 才能合成，那麼我們會連上 $X \rightarrow Y$ 的有向邊。這張圖的拓撲排序，就是一種取得物品的順序。
Course Schedule
給定一張圖，輸出他的拓撲排序。
如果不可能的話，輸出 IMPOSSIBLE。
條件限制
- $1 \le n \leq 10^5, 1 \le m \le 2 \times 10^5$
開啟寶盒
已知有 $n$ 個寶盒編號 $1$ 到 $n$ 以及 $m$ 種鑰匙編號 $1$ 到 $m$。一開始你有 $t$ 種鑰匙分別為 $x_1, x_2, \dots, x_t$。
每一個寶盒要打開都需要同時擁有 $k$ 種特定的鑰匙。每個寶盒打開後都會得到 $k$ 種鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過 $60$。
請輸出最多可以開啟多少個寶盒。
條件限制
- $1 \le n, m \le 10^5$
- $1 \le k \le 5$
Directing Edges
給一張圖，有一些邊是有向的，有一些邊則沒有方向。請將所有的邊指定一個方向，使得整張圖是有向無環圖。如果無解則輸出 "NO"，有解則輸出 "YES" 以及每條邊的方向。
總共有 $t$ 筆測資。
條件限制
- $1 \le t \le 2 \times 10^4$
- $\sum n, \sum m \le 2 \times 10^5$
- 沒有重邊和自環
汽車不再繞圈圈
給定一張有向圖，每一條邊有一個正整數權重 $c_i$。如果管理者有 $P$ 的權限，那麼他可以選擇反轉任意多條權重 $\le P$ 的邊，也可以不反轉。
請問最小需要多少權限，才能讓這張圖變成有向無環圖？若不需要改變任何道路方向就做得到，那麼答案是 $0$。
條件限制
- $2 \le n \le 10^5$
- $0 \le m \le 10^5$
- $c_i \le 10^9$