HDU 4324 Triangle LOVE：拓撲排序判環

問題

給定 n（≤ 2000）人的錦標賽圖（任意兩點間恰有一條有向邊）。判斷是否存在有向三環（A→B→C→A）。

關鍵定理

錦標賽圖無有向三環 ⇔ 圖是 DAG（有向無環圖） ⇔ 存在拓撲序。
故只需跑拓撲排序（Kahn 算法），若能輸出所有節點則無三環，否則有三環。

Kahn 算法

bool hasTriangle(int n, const vector& g) {
    vector indeg(n, 0);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (g[i][j] == '1') ++indeg[j];
    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 = 0; v < n; ++v)
            if (g[u][v] == '1' && --indeg[v] == 0) q.push(v);
    }
    return cnt != n; // 有環
}

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int n; cin >> n;
        vector g(n);
        for (int i = 0; i < n; ++i) cin >> g[i];
        vector indeg(n, 0);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (g[i][j] == '1') ++indeg[j];
        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 = 0; v < n; ++v)
                if (g[u][v] == '1' && --indeg[v] == 0) q.push(v);
        }
        cout << "Case #" << tc << ": " << (cnt == n ? "No" : "Yes") << '\n';
    }
    return 0;
}

複雜度

O(n²) 讀圖 + O(n²) 拓撲，n ≤ 2000 約 400 萬操作，極快。