HDU 3342 Legal or Not：拓撲排序判斷有向圖是否有環

題目大意

N, M ≤ 100。給定 M 條「師徒」關系 x y 表示 x 是 y 的師傅（有向邊 x→y）。判斷關系圖中是否存在環（非法）。合法輸出 YES，否則 NO。

拓撲排序判環

Kahn 算法：

1. 計算所有節點入度。
2. 入度為 0 的節點入隊。
3. 彈出節點，計數器 cnt++，減少後繼入度，入度歸 0 入隊。
4. 若最終 cnt == N → 無環（合法）；否則有環（非法）。

C++ 代碼

#include 
using namespace std;
const int MAXN = 105;
vector adj[MAXN];
int indeg[MAXN];

bool topo(int n) {
    queue q;
    for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ++cnt;
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    return cnt == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n) {
        for (int i = 0; i < n; ++i) { adj[i].clear(); indeg[i] = 0; }
        for (int i = 0; i < m; ++i) {
            int x, y; cin >> x >> y;
            adj[x].push_back(y);
            ++indeg[y];
        }
        cout << (topo(n) ? "YES" : "NO") << '\n';
    }
    return 0;
}

DFS 判環（備選）

vector state; // 0=未訪問,1=訪問中,2=已完成
bool hasCycle(int u) {
    state[u] = 1;
    for (int v : adj[u]) {
        if (state[v] == 1) return true; // 回邊
        if (state[v] == 0 && hasCycle(v)) return true;
    }
    state[u] = 2;
    return false;
}
// 主程序調用
state.assign(n, 0);
bool illegal = false;
for (int i = 0; i < n; ++i)
    if (state[i] == 0 && hasCycle(i)) { illegal = true; break; }

總結

HDU 3342 是「拓撲排序判環」的純模板題。Kahn 算法（BFS）代碼最短、無遞歸棧風險，推薦作為默認模板。同模板解決 POJ 1094、Codeforces 圖判環問題。