九度 OJ 1448 Legal or Not：拓撲排序判斷有向圖是否有環

九度 OJ 1448 Legal or Not：拓撲排序檢測環

題目大意

給定有向圖 n 點 m 邊，判斷是否存在環。輸出 Yes（有環）或 No（無環）。多組測資。

解法：Kahn 拓撲排序 (BFS)

1. 計算每點入度。
2. 將入度 0 點入佇列。
3. 彈出點，對其出邊終點入度 -1，若變 0 入佇列。
4. 計數輸出點數 cnt。若 cnt < n → 有環（Yes），否則 No。

完整程式碼（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector> g(n);
        vector indeg(n, 0);
        for (int i=0;i> u >> v;
            g[u].push_back(v);
            indeg[v]++;
        }
        queue q;
        for (int i=0;i

複雜度

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