POJ 2367 Genealogical Tree：拓樸排序入門經典題解

題目大意

火星人家族關係複雜：一個人可有多個父母、多個孩子。議會發言順序必須滿足：每個成員比其所有後代更早發言。給定 N（≤100）位成員及其子女列表，輸出任一合法的發言順序。

本質是有向無環圖（DAG）的拓樸排序：邊從父母指向子女，輸出滿足所有邊 u→v 中 u 在 v 之前的頂點序列。

輸入輸出範例

輸入：
5
0
4 5 1 0
1 0
5 3 0
3 0

輸出：
2 4 5 3 1

演算法一：Kahn 算法（BFS 入度法）

1. 計算所有節點入度。
2. 將入度為 0 的節點加入隊列。
3. 取出節點輸出，刪除其出邊（減少目標節點入度），新入度為 0 者入隊。
4. 重複直到隊列為空。

時間複雜度 O(N²)（N≤100 還可用鄰接矩陣）。

#include <cstdio>
#include <cstring>
const int MAXN = 110;
int map[MAXN][MAXN], in[MAXN], ans[MAXN], vis[MAXN];

int main() {
    int n, u;
    while (~scanf("%d", &n)) {
        memset(map, 0, sizeof(map));
        memset(in, 0, sizeof(in));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &u), u != 0) {
                map[i][u] = 1;
                in[u]++;
            }
        }
        int pos = 0;
        for (int k = 1; k <= n; k++) {
            int v = -1;
            for (int i = 1; i <= n; i++)
                if (!vis[i] && in[i] == 0) { v = i; break; }
            if (v == -1) break; // 有環（本題保證無環）
            vis[v] = 1;
            ans[pos++] = v;
            for (int j = 1; j <= n; j++)
                if (map[v][j]) in[j]--;
        }
        for (int i = 0; i < pos; i++)
            printf("%d%c", ans[i], i == pos-1 ? '\n' : ' ');
    }
    return 0;
}

演算法二：DFS 後序反轉法

1. 對每個未訪問節點執行 DFS。
2. DFS 過程中標記 vis[u] = -1（正在訪問），若遇到 vis[v] == -1 則有環。
3. 遞迴結束前將節點壓入堆疊 S.push(u)，標記 vis[u] = 1。
4. 最後堆疊彈出順序即為拓樸序。

#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = 110;
int vis[MAXN], map[MAXN][MAXN], n;
stack S;

bool dfs(int u) {
    vis[u] = -1;
    for (int v = 1; v <= n; v++) if (map[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));
    for (int u = 1; u <= n; u++)
        if (!vis[u] && !dfs(u)) return false;
    return true;
}

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

解題心得

• 圖小（N≤100）用鄰接矩陣最簡單，碼量少且不易出錯。
• DFS 法需注意三態標記（0=未訪、-1=訪問中、1=已完成）偵測環。
• 本題保證至少存在一解，故無環，任一合法序列皆可接受。