POJ 1094 拓撲排序：偏序關系動態判斷的經典實現

題目大意

給定 n 個大寫字母（n ≤ 26）和 m 條關系 A<B。逐條讀入關系，判斷：

• 某步驟後排序唯一確定 → 輸出 Sorted sequence determined after k relations: ...
• 出現矛盾（環） → 輸出 Inconsistency found after k relations.
• 所有關系讀完仍不唯一 → Sorted sequence cannot be determined.

算法：每步拓撲排序檢測

由於 n ≤ 26，每讀入一條邊就跑一次 Kahn 拓撲排序（O(n+m)），總複雜度 O(m(n+m)) ≤ 26×52 微乎其微。

拓撲排序判斷邏輯

1. 計算入度，將入度為 0 的節點入隊。
2. 若隊列大小 > 1 → 存在多種拓撲序（不唯一），標記 multiple = true。
3. 彈出節點，減少後繼入度，入度歸 0 入隊。
4. 若最終排序節點數 < n → 存在環（矛盾）。
5. 若無環且 !multiple → 排序唯一確定。

C++ 完整代碼

#include 
using namespace std;
const int MAXN = 30;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n || m) {
        vector> adj(n);
        vector indeg(n);
        vector> edges;
        int determined = -1, inconsistent = -1;
        string rel;
        for (int i = 0; i < m; ++i) {
            cin >> rel;
            int u = rel[0] - 'A', v = rel[2] - 'A';
            edges.emplace_back(u, v);
            if (determined != -1 || inconsistent != -1) continue;
            // 重建圖並拓撲
            fill(indeg.begin(), indeg.end(), 0);
            for (auto &e : edges) {
                adj[e.first].push_back(e.second);
                ++indeg[e.second];
            }
            queue q;
            for (int j = 0; j < n; ++j) if (indeg[j] == 0) q.push(j);
            vector seq;
            bool multi = false;
            while (!q.empty()) {
                if (q.size() > 1) multi = true;
                int u = q.front(); q.pop();
                seq.push_back(u);
                for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
            }
            if ((int)seq.size() < n) inconsistent = i + 1;
            else if (!multi) determined = i + 1;
            adj.assign(n, {}); // 清空供下輪
        }
        if (determined != -1) {
            cout << "Sorted sequence determined after " << determined << " relations: ";
            for (int x : seq) cout << char('A' + x);
            cout << ".\n";
        } else if (inconsistent != -1) {
            cout << "Inconsistency found after " << inconsistent << " relations.\n";
        } else {
            cout << "Sorted sequence cannot be determined.\n";
        }
    }
    return 0;
}

關鍵點

• 每輪重建圖簡單可靠，n 小時無需增量維護。
• 隊列大小 > 1 判斷「不唯一」是 Kahn 算法的經典技巧。
• 輸出格式嚴格：句號、空格、大小寫需完全匹配。

總結

POJ 1094 是「動態拓撲排序判斷」的教科書級題目。核心模板：Kahn 算法 + 隊列大小判唯一 + 節點數判環。同類模板適用於 HDU 1285、Codeforces 圖論判斷題。