floyd + topSort

$O(m * n^3)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 30, M = 100010;

int h[N], to[M], ne[M], idx;
int deg[N], ans[N]; //记录入度

bool d[N][N];

// d[i, j] = 1 表示 i < j
// 1. 若有 d[i, j] = d[j, i] = 1，则矛盾
// 2. 若有 d[i, j] = d[j, i] = 0，则存在未知
// 3. 若对所有(i, j)，都有 d[i, j] | d[j, i]，则关系确定

int n, m;

void add(int a, int b){
    to[++idx] = b, ne[idx] = h[a], h[a] = idx;
    deg[b] += 1;
}

void topSort(){
    queue<int> q;
    for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
    int t = 0;

    while(q.size()){
        int x = q.front(); q.pop();
        ans[++t] = x;
        for(int i = h[x]; i; i = ne[i]){
            int y = to[i];
            if(--deg[y] == 0) q.push(y);
            }
        }

    for(int i = 1; i <= t; i++) printf("%c", ans[i] + 'A' - 1);
    puts(".");
}

int main(){
    while(scanf("%d %d", &n, &m), n || m){
        memset(d, 0, sizeof(d));
        memset(h, 0, sizeof(h));
        memset(deg, 0, sizeof(deg));
        idx = 0;

        int flag = 2, t = m;    //flag = 2 表示关系还没确定
        for(int p = 1; p <= m; p++){
            char s[5];
            scanf("%s", s);
            if(flag == 1 || flag == 3) continue;

            int x = s[0] - 'A' + 1, y = s[2] - 'A' + 1;
            d[x][y] = 1;

            // floyd传递闭包
            for(int k = 1; k <= n; k++)
                for(int i = 1; i <= n; i++)
                    for(int j = 1; j <= n; j++)
                        d[i][j] |= d[i][k] & d[k][j];

            // check
            int check = 3; // 3表示全部关系都确定了
            for(int i = 1; i <= n; i++){
                for(int j = i + 1; j <= n; j++){
                    if(d[i][j] == 1 && d[j][i] == 1){
                        check = 1;
                        t = p;
                        break;
                        }
                    if(d[i][j] == 0 && d[j][i] == 0){
                        check = 2;
                        break;
                        }
                    }
                if(check == 1) break;
                }

            if(check == 1) flag = 1;
            if(check == 2) add(x, y);
            if(check == 3) add(x, y), flag = 3, t = p;
            }

        if(flag == 1){
            printf("Inconsistency found after %d relations.\n", t);
            }
        else if(flag == 2){
            puts("Sorted sequence cannot be determined.");
            }
        else if(flag == 3){ //关系确定，构成拓扑序
            printf("Sorted sequence determined after %d relations: ", t);   
            topSort();
            }
        }
    return 0;
}