【图论，拓扑排序】P1347 排序

题意

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

输入格式

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

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

输出格式

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

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

其中 $x$ 表示上述的前 $x$ 个关系，注意 relations: 与输出的顺序中有一个空格

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

Inconsistency found after x relations.

其中 $x$ 表示的意义同上。

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

Sorted sequence cannot be determined.

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

说明/提示

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

思路

oi wiki 的拓扑排序介绍，建议先浏览。

本文是每加入一条边后进行一次拓扑排序，然后判断出现环、有多个入度为0的点还是能拍出顺序。

小细节：

• 要先判断环再判断有多个入度为0的点，也就是你拓扑排序中不能一遇到有2个入度为0的点就停止排序进行下一条边的读入。

• 环的判断要求是比较已经排好顺序的点和目前出现的所有点比较，而非同一共的点数 $n$ 比较。

• 本题需要拓扑排序多次，排序需要的入度数组建议另行复制一个，以免影响原数组。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[30],nex[1005],to[1005],cnt = 0,now_P;
int in[30];//点入度
bool vis[35];
void add(int x,int y) {nex[++cnt] = head[x];head[x] = cnt;to[cnt] = y;in[y]++;if(!vis[x]) now_P ++;if(!vis[y]) now_P++;vis[x] = 1,vis[y] = 1;
}
int sx[30],tpin[30];//顺序 int tp() {int t = 0;bool k = 0;//判断是否出现有两个入度为0的情况queue<int>point;for(int i = 0;i <= 25;i++) {tpin[i] = in[i];//复制入度if(tpin[i] == 0 and vis[i]) point.push(i);}while(!point.empty()) {int P = point.front();point.pop();if(!point.empty()) k = 1;sx[++t] = P;for(int i = head[P];i;i = nex[i]) {tpin[to[i]]--;if(tpin[to[i]] == 0) point.push(to[i]);}//printf("______%lld %lld\n",P,t);}if(t < now_P) return 0;//出现环if(k) return 2;return 1;
}
signed main() {scanf("%d %d",&n,&m);for(int i = 1;i <= m;i++) {char p,r,q;cin >> p >> r >> q;add(int(q - 'A'),int(p - 'A'));int result = tp();if(result == 0) {printf("Inconsistency found after %d relations.\n",i);return 0;}else if(result == 1 and now_P == n) {printf("Sorted sequence determined after %d relations: ",i);for(int j = n;j >= 1;j--) cout<<char(sx[j] + 'A');cout<<'.';return 0;}}printf("Sorted sequence cannot be determined.\n");return 0;
}