題意#
為了順利畢業，你必須完成修讀 \(n\) 門課程。然而這其中有 \(m\) 個「擋修限制（Requirements）」，形式為「課程 A 必須在課程 B 之前修完」。
你的任務是找出一組能順利把這 \(n\) 門課全部修完的「合法修課順序」（如果有好幾種排法，輸出任意一種即可）。如果這些擋修條件之間出現了不合理的死胡同（例如互擋），導致根本不可能修完，請印出 IMPOSSIBLE。
思路#
看到「有次序依賴關係的任務排程」，二話不說，直接掏出拓樸排序（Topological Sort）就對了。
實作拓樸排序最經典也最直覺的演算法就是 Kahn’s Algorithm，它的概念完美對應了我們先修課的邏輯：
- 為每一門課程計算「入度（In-degree）」，也就是這門課前面總共有幾門擋修課。
- 尋找所有「入度為 0」（沒有被任何課擋住，可以直接修）的課程，把它們通通丟進一個佇列（Queue）中當作開局。
- 開始迴圈！每次從佇列中抽出一門課，把它加進我們的畢業課表（答案陣列）。然後「拔掉」這門課的影響力 —— 也就是去檢查所有被這門課擋到的後續課程，將它們的入度減 1。
- 在減 1 的過程中，如果發現某門課程的入度剛好歸零了（代表所有擋修條件都滿足了），就立刻把它加進佇列中等待上課。
迴圈跑完後，我們只要確認一下排出來的畢業課表是不是剛好包含了所有的 \(n\) 門課。如果數量不夠，就代表有課程陷入了「互擋（循環依賴）」的詭異迴圈裡，也就是無解。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m; cin >> n >> m;
// w 陣列用來記錄每門課的「入度（被擋的次數）」
vector<int> w(n+1);
vector<vector<int>> g(n+1); // 記錄有向圖
// 建立排課依賴關係圖
while (m--) {
int a, b; cin >> a >> b;
g[a].pb(b); // a 是 b 的先修課
w[b]++; // b 身上又多了一個擋修條件
}
queue<int> q;
vector<int> ans; // 存放最終排好的畢業課表
// 開局先掃過一遍，把所有沒有擋修課（入度為 0）的課程推進佇列
for (int i = 1; i <= n; i++) if (!w[i]) q.push(i);
// Kahn's Algorithm 核心邏輯
while (q.size()) {
ans.pb(q.front()); // 把這門課加入課表
// 拔除這門課對後續課程的擋修影響
for (auto u : g[q.front()]) {
// 如果後續課程的擋修條件全部解除（歸零），就推入佇列準備修習
if (!(--w[u])) q.push(u);
}
q.pop();
}
// 檢查是不是所有課都修完了（沒有卡在循環死胡同中）
if (ans.size() == n) {
for (auto &i : ans) cout << i << ' ';
}
else {
cout << "IMPOSSIBLE\n";
}
}
