POJ 2367 Genealogical tree：拓撲排序輸出合法發言順序

問題

N（≤ 100）個火星人，每行列出其子女。要求輸出一個順序，使每人比其所有後代更早發言。多解任意輸出一個。

拓撲排序 (Kahn)

邊方向：父 → 子。入度為 0 的節點無父親，可最先輸出。
反覆取入度 0 節點輸出，刪除其出邊，直到所有節點輸出完畢。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int g[MAXN][MAXN], indeg[MAXN], ans[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        memset(g, 0, sizeof(g)); memset(indeg, 0, sizeof(indeg));
        for (int i = 1; i <= n; ++i) {
            while (true) {
                int c; cin >> c;
                if (c == 0) break;
                g[i][c] = 1; ++indeg[c];
            }
        }
        queue q;
        for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);
        int idx = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop(); ans[idx++] = u;
            for (int v = 1; v <= n; ++v)
                if (g[u][v] && --indeg[v] == 0) q.push(v);
        }
        for (int i = 0; i < n; ++i) {
            if (i) cout << ' '; cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

複雜度

O(n²) 讀圖 + O(n²) 拓撲，n ≤ 100 極快。