HDU 1285：確定比賽名次——拓撲排序模板題

問題描述

給定一個有向無環圖 (DAG)，節點代表參賽者，邊 u → v 表示 u 排名優於 v。輸出滿足所有約束的拓撲序列（若多解，輸出字典序最小/任意合法序列均可，本題無特殊要求）。

拓撲排序 (Kahn 算法 / BFS 版)

1. 計算每個節點的入度 in[v]。
2. 將入度為 0 的節點加入隊列/優先隊列。
3. 重複：取出節點 u 輸出，遍歷其出邊 u → v，in[v]--，若變 0 入隊。
4. 若輸出節點數 < n，說明有環（本題保證無環）。

代碼實現 (C++)

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 505;
int mat[MAXN][MAXN], in[MAXN];
int n, m;

void topological_sort() {
    int cnt = n;
    while (cnt--) {
        int u = 1;
        while (u <= n && in[u] != 0) ++u; // 找入度為0的點
        printf("%d", u);
        in[u] = -1; // 標記已輸出
        if (cnt) printf(" ");
        for (int v = 1; v <= n; ++v)
            if (mat[u][v]) in[v]--;
    }
    printf("\n");
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        memset(mat, 0, sizeof(mat));
        memset(in, 0, sizeof(in));
        for (int i = 0; i < m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            if (!mat[u][v]) { mat[u][v] = 1; in[v]++; }
        }
        topological_sort();
    }
    return 0;
}

複雜度

• 時間：O(n²) 適用於 n ≤ 500 的鄰接矩陣存儲；若邊稀疏可改用鄰接表 O(n+m)。
• 空間：O(n²)。

擴展：字典序最小拓撲序

將隊列改為 priority_queue<int, vector<int>, greater<int>>（小根堆），每次取最小可用節點。