HDU 5154 Harry and Magical Computer：拓撲排序判環

題目大意

給定 n（≤100）個進程與 m（≤10000）條依賴關係（a, b 表示 b 必須在 a 之前完成），判斷是否能完成所有進程（即有向圖是否為 DAG）。

解題思路

經典拓撲排序判環：統計每個節點入度，將入度為 0 的節點加入佇列，依次刪除並更新鄰居入度。若最終刪除節點數等於 n，則無環，輸出 YES；否則 NO。

代碼實現

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

struct Edge { int u, v, next; } edge[1100000];
int head[1000000], rudu[200000], vis[200000], cnt, n;

void add(int u, int v) {
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void topo() {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (rudu[i] == 0) { q.push(i); vis[i] = 1; }

    int processed = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ++processed;
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].v;
            if (--rudu[v] == 0 && !vis[v]) {
                q.push(v);
                vis[v] = 1;
            }
        }
    }
    puts(processed == n ? "YES" : "NO");
}

int main() {
    int m;
    while (~scanf("%d%d", &n, &m)) {
        cnt = 0;
        memset(head, -1, sizeof(head));
        memset(rudu, 0, sizeof(rudu));
        for (int i = 0; i < m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            add(u, v);
            ++rudu[v];
        }
        topo();
    }
    return 0;
}

複雜度

• 時間：O(n + m)
• 空間：O(n + m)

注意事項

• 多測資讀至 EOF。
• 節點編號從 1 開始，陣列大小需足夠（m 最大 10000，邊數雙向儲存需 20000）。
• 拓撲排序亦可用 DFS 三色標記法，但 BFS 寫法更直觀。