UVA 10305 Ordering Tasks：拓撲排序的 DFS 實現

問題描述

給定一個有向無環圖（DAG），節點編號 1..n，邊表示任務依賴關係（x y 表示 x 必須在 y 之前完成）。輸出一個合法的拓撲序列。題目保證無環，且 n ≤ 100。

DFS 拓撲排序原理

對每個未訪問節點執行 DFS，遞歸訪問其所有出鄰接點，退遞歸時將節點壓入棧（或記錄到數組尾部）。最終逆序即為拓撲序。因為題目保證無環，無需檢測環。

代碼實現 (C)

#include <stdio.h>
#include <string.h>

int map[105][105];
int visit[105];
int order[105];
int n, m, top;

void dfs(int u) {
    visit[u] = 1;
    for (int v = 1; v <= n; v++)
        if (!visit[v] && map[v][u]) // 注意：map[v][u] 表示 v→u，u 依賴 v
            dfs(v);
    order[top++] = u;
}

int main() {
    while (scanf("%d%d", &n, &m), n||m) {
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        top = 0;
        for (int i=0;i<m;i++) {
            int x,y; scanf("%d%d",&x,&y);
            map[x][y] = 1; // x→y
        }
        for (int i=1;i<=n;i++)
            if (!visit[i]) dfs(i);
        for (int i=top-1;i>=0;i--) {
            printf("%d", order[i]);
            if (i) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

關鍵點

• 鄰接矩陣 map[x][y]=1 表示 x 在 y 之前。
• DFS 參數傳遞當前節點，遞歸訪問其「前驅」（即 map[v][u]），這與常規「訪問後繼」相反，但邏輯等價。
• 輸出時逆序（從 top-1 到 0）。

複雜度

時間 O(n^2)（鄰接矩陣掃描），空間 O(n^2)，n≤100 完全足夠。若用鄰接表可優化至 O(n+m)。

總結

UVA 10305 是拓撲排序的入門經典題。DFS 版本代碼極短，適合快速寫出。掌握「逆後序即拓撲序」的核心思想，並注意圖的存儲方式對遞歸方向的影響。