HDU 1285 確定比賽名次：拓撲排序與優先隊列優化

問題描述

有 n 支隊伍，m 條比賽結果 a b 表示隊伍 a 勝過 b。要求輸出一個合法的排名序列，滿足：若存在從 u 到 v 的有向路徑，則 u 必須排在 v 前面。若有多解，編號小的隊伍優先輸出。

拓撲排序基本原理

對於有向無環圖（DAG），拓撲排序是將所有頂點線性排序，使得所有有向邊 u → v 中 u 都在 v 之前。Kahn 算法流程：

1. 統計每個頂點的入度（指向它的邊數）
2. 將所有入度為 0 的頂點加入隊列
3. 重複：取出隊列頂點 u 輸出，刪除其出邊，若某頂點 v 入度變為 0 則入隊
4. 若最終輸出頂點數 < n，說明圖中有環

優先隊列優化：保證編號小優先

題目要求「編號小的隊伍在前」，只需將普通隊列改為 最小堆（優先隊列），每次取出當前入度為 0 的最小編號頂點即可。

參考代碼：基礎版（鄰接矩陣）

#include <iostream>
#include <cstring>
using namespace std;

int map[502][502], indeg[502], val[502];
int n, m;

void topsort() {
    int k = 1;
    for (int i = 1; i <= n; i++) { // 需選 n 次
        for (int j = 1; j <= n; j++) {
            if (indeg[j] == 0) { // 找入度為 0
                indeg[j] = -1; // 標記已用
                val[k++] = j;
                for (int x = 1; x <= n; x++) // 刪除出邊
                    if (map[j][x]) indeg[x]--;
                break;
            }
            if (j > n) return; // 有環
        }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(map, 0, sizeof(map));
        memset(indeg, 0, sizeof(indeg));
        for (int i = 1; i <= m; i++) {
            int a, b; cin >> a >> b;
            if (!map[a][b]) { map[a][b] = 1; indeg[b]++; }
        }
        topsort();
        for (int i = 1; i <= n; i++)
            cout << val[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

參考代碼：優化版（鄰接表 + 優先隊列）

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 510;
vector g[N];
int indeg[N], val[N];
int n, m;

void topsort() {
    priority_queue, greater> q; // 最小堆
    for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);
    int cnt = 1;
    while (!q.empty()) {
        int u = q.top(); q.pop();
        val[cnt++] = u;
        for (int v : g[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
}

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(indeg, 0, sizeof(indeg));
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 1; i <= m; i++) {
            int u, v; scanf("%d %d", &u, &v);
            g[u].push_back(v);
            indeg[v]++;
        }
        topsort();
        for (int i = 1; i <= n; i++)
            printf("%d%c", val[i], i == n ? '\n' : ' ');
    }
    return 0;
}

複雜度對比

關鍵點總結

1. 拓撲排序核心是「入度為 0 的點沒有前驅，必須排在最前」
2. 優先隊列天然滿足「編號小優先」的輸出要求
3. 注意圖中可能有重複邊，建圖時去重