圖論基礎練習：基於拓撲排序判斷有向圖是否存在環（Kahn 算法實現）

題目大意

給定有向圖 n≤10 點 m 邊，判斷是否存在合法拓撲序列（即是否為 DAG）。多測試用例。

Kahn 算法

1. 計算所有頂點入度。
2. 重複：找入度為 0 的頂點，輸出/刪除（入度設 -1），其出邊指向頂點入度 -1。
3. 若某輪無入度 0 頂點但仍有未刪除頂點，則存在環，輸出 NO。
4. 若所有頂點成功刪除，輸出 YES。

C 代碼實現

#include <stdio.h>
#include <string.h>
int n, m, map[20][20], in[20];
void topo() {
    int i, j, k, flag;
    for (i=1;i<=n;i++) {
        flag=0;
        for (j=1;j<=n;j++) if (in[j]==0) {
            flag=1; in[j]=-1;
            for (k=1;k<=n;k++) if (map[j][k]) in[k]--;
            break;
        }
        if (!flag) break;
    }
    puts(flag?"YES":"NO");
}
int main() {
    int u, v;
    while (~scanf("%d%d",&n,&m)) {
        memset(map,0,sizeof(map));
        memset(in,0,sizeof(in));
        while (m--) { scanf("%d%d",&u,&v); map[u][v]=1; in[v]++; }
        topo();
    }
    return 0;
}

複雜度

O(n^2)，n≤10 極快。