POJ 1094 Sorting It All Out：拓撲排序判斷序列確定性與一致性

題目大意

給 n (≤ 26) 個大寫字母，m 條關係 A<B。按輸入順序逐條加入關係，判斷：
1. Inconsistency：出現環（矛盾）。
2. Sorted sequence determined：拓撲序唯一（每步隊列中僅有一個入度為 0 的點）。
3. Cannot be determined：處理完所有關係仍無法確定唯一序列。

核心算法：Kahn 拓撲排序 + 唯一性判斷

• 維護鄰接矩陣 g[27][27] 和入度 deg[27]。
• 每加入一條邊，跑一次拓撲排序：
  - 用隊列存入度為 0 的點。
  - 若隊列曾為空 → 有環 → Inconsistency。
  - 若隊列曾有 ≥2 個點 → 序列不唯一。
  - 若成功輸出 n 個點且隊列始終唯一 → Sorted sequence determined。

關鍵代碼片段

int topo(int n) {
    int tmp[27], q[27], qh=0, qt=0;
    for (int i=1;i<=n;++i) tmp[i]=deg[i];
    for (int i=1;i<=n;++i) {
        int cnt=0, u=0;
        for (int j=1;j<=n;++j) if (tmp[j]==0) { cnt++; u=j; }
        if (cnt==0) return 0; // 有環
        if (cnt>1) return -1; // 不唯一
        q[qt++] = u;
        tmp[u] = -1;
        for (int v=1;v<=n;++v) if (g[u][v]) tmp[v]--;
    }
    return 1; // 唯一
}

主流程

while (scanf("%d%d", &n, &m), n||m) {
    memset(g,0,sizeof(g)); memset(deg,0,sizeof(deg));
    bool done = false;
    for (int i=1; i<=m; ++i) {
        char s[4]; scanf("%s", s);
        if (done) continue;
        int a=s[0]-'A'+1, b=s[2]-'A'+1;
        if (!g[a][b]) { g[a][b]=1; deg[b]++; }
        int res = topo(n);
        if (res == 0) {
            printf("Inconsistency found after %d relations.\n", i);
            done = true;
        } else if (res == 1) {
            printf("Sorted sequence determined after %d relations: ", i);
            for (int j=0;j