POJ 2367 Genealogical Tree：拓撲排序入門經典雙解法

題目大意

N 個火星人 (1..N)，給出每個人的孩子列表。要求輸出一個序列，使每個人都在其所有後代之前發言。即拓撲排序：有向圖中邊 u→v 表示 u 是 v 的祖先，輸出滿足所有邊 u 在 v 前的頂點序列。

輸入格式

N
第1行: 1的孩子列表，以0結束
第2行: 2的孩子列表...
...
第N行: N的孩子列表

解法一：Kahn 算法 (BFS + 入度)

#include 
#include 

const int MAXN = 110;
int g[MAXN][MAXN], indeg[MAXN], ans[MAXN], vis[MAXN];

int main() {
    int n, u;
    while (~scanf("%d", &n)) {
        memset(g, 0, sizeof(g));
        memset(indeg, 0, sizeof(indeg));
        memset(vis, 0, sizeof(vis));
        
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &u), u) g[i][u] = 1;
        }
        
        // 計算入度
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (g[i][j]) indeg[j]++;
        
        int cnt = 0;
        for (int iter = 0; iter < n; iter++) {
            int u = 0;
            for (int i = 1; i <= n; i++)
                if (!vis[i] && indeg[i] == 0) { u = i; break; }
            
            vis[u] = 1;
            ans[cnt++] = u;
            for (int v = 1; v <= n; v++)
                if (g[u][v]) indeg[v]--;
        }
        
        for (int i = 0; i < cnt; i++)
            printf("%d%c", ans[i], i==cnt-1?'\n':' ');
    }
    return 0;
}

解法二：DFS + 棧 (遞歸後序)

#include 
#include 
#include 
using namespace std;

const int MAXN = 110;
int g[MAXN][MAXN], vis[MAXN], n;
stack S;

bool dfs(int u) {
    vis[u] = -1;  // 正在訪問
    for (int v = 1; v <= n; v++) if (g[u][v]) {
        if (vis[v] == -1) return false;  // 環檢測（本題保證無環）
        if (!vis[v] && !dfs(v)) return false;
    }
    vis[u] = 1;  // 訪問完成
    S.push(u);   // 後序入棧
    return true;
}

bool toposort() {
    memset(vis, 0, sizeof(vis));
    while (!S.empty()) S.pop();
    for (int u = 1; u <= n; u++)
        if (!vis[u] && !dfs(u)) return false;
    return true;
}

int main() {
    int u;
    while (~scanf("%d", &n)) {
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; i++)
            while (scanf("%d", &u), u) g[i][u] = 1;
        
        if (toposort()) {
            int t = n;
            while (!S.empty()) {
                printf("%d%c", S.top(), --t?' ':'\n');
                S.pop();
            }
        }
    }
    return 0;
}

兩種方法對比

樣例驗證

Input:
5
0
4 5 1 0
1 0
5 3 0
3 0

邊: 2→4, 2→5, 2→1, 3→1, 4→5, 4→3, 5→3

Output: 2 4 5 3 1 (或其他合法拓撲序)

核心知識點總結

1. 拓撲排序定義：DAG 的線性排序，使所有邊 u→v 滿足 u 在 v 前
2. 存在性條件：圖必須是 DAG (無環)，本題保證至少一解
3. 非唯一性：多個合法序列，任意輸出一個即可
4. 應用場景：任務調度、編譯依賴、課程先修、構建系統

擴展練習

• 輸出字典序最小拓撲序 (用優先隊列)
• 判斷圖中是否有環
• 計算所有合法拓撲序數量 (DP on DAG)
• 動態添加邊後維護拓撲序