发一个码风正常好看，思路清晰的题解。

如果喷解题人能使你开心，请尽情地喷解题人。

题目描述

不多阐述了，自己看题。

算法 $1$

拓扑排序，自己看别的题解，这里不解释。

算法 $2$

因为有关系传递性的存在，可以用 Floyd 传递闭包进行求解。

设 $e(x,y)$ 表示 $x$ 和 $y$ 的关系，若 $x$ 小于 $y$，那么 $e(x,y) = 1$，否则 $e(x,y)=0$。

对于 Floyd 的传递方程是

$$ e(x,y) = e(x,y)\ \text{or}\ (e(x,z)\ \text{and}\ e(z,y)) $$

表示当 $x<z$ 且 $z<y$ 时，有 $x<y$。

$\text{and}$ 限制了两个条件都要符合，$\text{or}$ 实际是若两个条件都符合，那么更新为 1，否则为 0。

若当前 $i$ 个不等式矛盾，则必定存在 $x$ 和 $y$，使 $e(x,y)=e(y,x)=1$。

若当前 $i$ 个可以确定关系，那么必定任意 $x$ 和 $y$，$e(x,y)$ 和 $e(y,x)$ 两者有且仅一个是 1。

判断 $m$ 个不等式无法确定关系，那么存在 $x$ 和 $y$，使 $e(x,y)=e(y,x)=0$。

因为矛盾和确定关系需要输出在第几个不等式后，所以输入的每个不等式，都要进行一次 Floyd。

对于可以确定输出排序后结果的实现，可以 $O(n^2)$ 来得到。即对于 x，遍历数组记录小于 $x$ 的数量 $cnt$，则 $x$ 就在从左往右第 $cnt-1$ 个位置上。

剩下的就是简单的实现了，不再多阐述。

注意

• 要先判矛盾再判是否可以确定关系。

• 空间比较小，注意数组大小。

时间复杂度 $O(mn^3)$。

代码

#include<bits/stdc++.h>

#define ll long long
#define y1 caibictq
#define P pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 51;
const int MAXM = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m;
int tot, cnt;

int ans[MAXN];

int read() {
    int f = 1, s = 0;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 1) + (s << 3) + ((int)ch ^ 48); ch = getchar();}
    return s * f;
}

int a[MAXN], b[MAXN];
int e[MAXN][MAXN];

string s[MAXM];

void Floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                e[i][j] |= e[i][k] & e[k][j];
            }
        }
    }
    return;
}

bool Contradiction() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (e[i][j] && e[j][i]) return 1;
        }
    }
    return 0;
}

bool Sorted() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (e[i][j] && e[j][i]) return 0;
            if (!e[i][j] && !e[j][i]) return 0;
        }
    }
    return 1;
}

void Solve() {
    for (int i = 1; i <= n; i++) {
        int tmp = 1;
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (e[j][i]) ++tmp;
        }
        ans[tmp - 1] = ('A' + i - 1);
    }
    return;
}

void print() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", e[i][j]);
        }
        puts("");
    }
}

int main() {
    int T;
    while (scanf("%d%d", &n, &m) && n && m) {
        int ok = 0;
        memset(e, 0, sizeof(e));
        for (int i = 1; i <= m; i++) {
            cin >> s[i];
            if (ok) continue; 
            int u = s[i][0] - 'A' + 1, v = s[i][2] - 'A' + 1;
            e[u][v] = 1;
            Floyd();
            if (Contradiction()) {
                printf("Inconsistency found after %d relations.\n", i);
                ok = 1;
            }
            if (!Sorted()) continue; 
            Solve();
            printf("Sorted sequence determined after %d relations: ", i);
            for (int j = 0; j < n; j++) printf("%c", (char)ans[j]);
            puts(".");
            ok = 1;
        }
        if (ok) continue;
        printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}