一、學習目標

• 了解拓撲排序的兩種常見實作：Kahn’s Algorithm（BFS／入度法） 與 DFS 反向後序。
• 能用拓撲序判斷是否為 DAG（有無有向環）、並在 DAG 上做 DP（最長路／路徑數）。
• 熟悉細節：入度初始化、佇列進出、重邊、自環、1-index/0-index、字典序最小解。

二、觀念說明

什麼是拓撲序

對有向無環圖（DAG），存在一個節點排列，使得每條邊 u → v 皆滿足 u 在 v 之前。
若圖中有有向環，則拓撲序不存在。

兩種主流作法

1. Kahn’s Algorithm（入度法，BFS）

• 入度：indeg[v] = 指向 v 的邊數。
• 流程：
  • 計算所有點入度，將入度為 0 的點推入佇列（可用 queue；若要字典序最小，用 priority_queue 小根堆）；
  • 反覆彈出隊首 u 加入答案，並將 u 的所有出邊 (u→v) 的 indeg[v]--；
  • 若 indeg[v] 變成 0，將 v 推入佇列；
  • 最後若取出的節點數 = n，則有拓撲序；否則圖中存在環。

2. DFS 後序反轉

• 對每個未訪點做 DFS，回溯時把節點壓入序列，最後反轉序列即為拓撲序。
• 若 DFS 遇到「回邊」（在遞迴中再次訪到灰色點），代表有環。
• 同樣 O(n+m)，但在某些題目（例如要找環）時寫起來直覺。
• 競賽常用 Kahn，因為可自然處理「多源入度 0」及字典序最小。

三、CSES實戰演練

題目1:Course Schedule

原題:
https://cses.fi/problemset/task/1679

題意
給 n 門課（1…n）與 m 條先修關係 a → b（修 a 才能修 b）。
請輸出一個可行的修課順序；若不存在（有向環）則輸出 IMPOSSIBLE。

解題思路

• 典型 Kahn：建圖與入度，佇列收入度 0 的課。
• 每取出一課，就把其出邊對應課程入度遞減，入度變 0 就入列。
• 結束時若收集到的課程數 < n，代表有環 → IMPOSSIBLE。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    vector<int> indeg(n+1, 0);
    while(m--){
        int a, b; cin >> a >> b; // a -> b
        g[a].push_back(b);
        indeg[b]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++) if(indeg[i]==0) q.push(i);

    vector<int> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);
        for(int v: g[u]){
            if(--indeg[v]==0) q.push(v);
        }
    }
    if((int)order.size()!=n){
        cout << "IMPOSSIBLE\n";
    }else{
        for(int i=0;i<n;i++)
            cout << order[i] << (i+1==n?'\n':' ');
    }
    return 0;
}

題目2:Game Routes

原題:
https://cses.fi/problemset/task/1681

題意:
給定一張有向無環圖（DAG），求從節點 1 到節點 n 的不同路徑數

解題思路:

• 先用 Kahn 取得拓撲序。
• DP：dp[1]=1，依拓撲序把 dp[u] 加到所有出鄰 v：dp[v] = (dp[v]+dp[u]) % MOD。
• 最後輸出 dp[n]。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    vector<int> indeg(n+1, 0);
    while(m--){
        int a,b; cin >> a >> b;
        g[a].push_back(b);
        indeg[b]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++) if(indeg[i]==0) q.push(i);

    vector<long long> dp(n+1, 0);
    dp[1] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: g[u]){
            dp[v] += dp[u];
            if(dp[v] >= MOD) dp[v] -= MOD;
            if(--indeg[v]==0) q.push(v);
        }
    }
    cout << dp[n] % MOD << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Course Schedule

原題:
https://leetcode.com/problems/course-schedule/description/

題意:
numCourses 門課（0…n-1）與先修關係 prerequisites[i] = [a, b]（修 b 才能修 a）。
問是否能修完全部課（是否存在拓撲序）。

解題思路:

• 用 Kahn 判環：若最終出列的課數 = numCourses，回傳 true，否則 false。
• 也可用 DFS（顏色/遞迴棧）判環。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        vector<int> indeg(numCourses, 0);
        for(auto &e: prerequisites){
            int a=e[0], b=e[1]; // b -> a
            g[b].push_back(a);
            indeg[a]++;
        }
        queue<int> q;
        for(int i=0;i<numCourses;i++) if(indeg[i]==0) q.push(i);

        int taken = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            taken++;
            for(int v: g[u]){
                if(--indeg[v]==0) q.push(v);
            }
        }
        return taken == numCourses;
    }
};

題目2:Course Schedule II

原題:
https://leetcode.com/problems/course-schedule-ii/

題意:
同上題，但需要輸出一個可行的修課順序。若不存在（有環）回傳空陣列。

解題思路:

• 直接 Kahn：把出列順序記錄下來。
• 若需要字典序最小，用小根堆取代佇列即可（題目不要求）。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        vector<int> indeg(numCourses, 0);
        for(auto &e: prerequisites){
            int a=e[0], b=e[1]; // b -> a
            g[b].push_back(a);
            indeg[a]++;
        }
        queue<int> q;
        for(int i=0;i<numCourses;i++) if(indeg[i]==0) q.push(i);

        vector<int> order;
        while(!q.empty()){
            int u = q.front(); q.pop();
            order.push_back(u);
            for(int v: g[u]){
                if(--indeg[v]==0) q.push(v);
            }
        }
        if((int)order.size()!=numCourses) return {};
        return order;
    }
};