洛谷P1347 排序题解

题意：

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示$A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式：

第一行有两个正整数 $n,m$，$n$ 表示需要排序的元素数量，$2\leq n\leq 26$，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D\dots$ 表示。$m$ 表示将给出的形如 $A<B$ 的关系的数量。

接下来有 $m$ 行，每行有 $3$ 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式：

若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$），输出

Inconsistency found after x relations.

若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 $n$ 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

数据范围：

$2 \leq n \leq 26,1 \leq m \leq 600$。

这里的确定关系等价于拓扑序唯一。

如果拓扑序唯一，那么任意一层均不存在多个元素，或者更简单的，最深层深度为 $n$ 。

如果存在矛盾，即存在环，那么拓扑排序一定不能遍历所有点。这个很好判。

如果又不是无解又不能确定拓扑序，即到最后也不是情况一或二，那就对应第三种情况。

因为它要问最早啥时候出现结果，所以每次加边都要跑一遍拓扑排序。

时间复杂度 $\mathcal{O}(mn^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(35))
#define M ((int)(615))

char s[16];
int n,m,pos=1,head[N],f[N],in[N],tin[N],stk[N];
struct Edge { int u,v,next; } e[M];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; }
int topo()
{
    queue<int> q; for(int i=1; i<=n; i++)tin[i] = in[i], f[i] = 0;
    for(int i=1; i<=n; i++) if(!tin[i]) { q.push(i), f[i] = 1; }
    int cnt = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); stk[++cnt] = u;
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v; up(f[v], f[u] + 1);
            if(!(--tin[v])) q.push(v);
        }
    }
    if(cnt < n) return -1;
    if(*max_element(f + 1, f + 1 + n) == n) return 1;
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> s; u = s[0] - 'A' + 1; v = s[2] - 'A' + 1;
        addEdge(u,v); ++in[v]; int res = topo();
        if(res == -1)
        { cout << "Inconsistency found after " << i << " relations.\n"; return 0; }
        else if(res == 1)
        {
            cout << "Sorted sequence determined after " << i <<  " relations: ";
            for(int j=1; j<=n; j++) cout << char(stk[j] + 'A' - 1); cout << ".\n";
            return 0;
        }
    }
    cout << "Sorted sequence cannot be determined.\n";
    return 0;
}