那题有点坑啊,还是过了。
by L2_sheep @ 2018-11-29 15:51:13
```cpp
#include <stdio.h>
#define N 26
int main()
{
int n, m, a, b, i, t, tt, u, v, j, k;
int ta[N], tb[N], la, lb, d[N][N], x[N][N], tn;
while(scanf("%d%d", &n, &m) && n){
int cd[N] = {0}, cx[N] = {0}, fs = 0, fi = 0;
char f[N][N] = {0}, s[5];
tn = n - 1;
for(i = 1; i <= m; i++){
scanf("%s", s);
if(fi || fs) continue;
a = s[0] - 65, b = s[2] - 65;
for(j = 0, la = cx[a]; j < la; j++) ta[j] = x[a][j];
ta[la] = a;
for(j = 0, lb = cd[b]; j < lb; j++) tb[j] = d[b][j];
tb[lb] = b;
for(j = 0; j <= la; j++){
for(k = 0; k <= lb; k++){
u = ta[j], v = tb[k];
if(!f[u][v]){
d[u][cd[u]++] = v;
x[v][cx[v]++] = u;
f[u][v] = 1, f[v][u] = 2;
}
else{
if(f[u][v] == 2){
fi = i;
break;
}
}
}
if(fi) break;
}
if(fi || fs) continue;
for(j = 0; j < n; j++){
if(cd[j] + cx[j] != tn) break;
}
if(j == n) fs = i;
}
if(fi){
printf("Inconsistency found after %d relations.\n", fi);
continue;
}
if(!fs){
puts("Sorted sequence cannot be determined.");
continue;
}
printf("Sorted sequence determined after %d relations: ", fs);
for(j = 0; j < n; j++){
for(k = 0; cx[k] != j; k++);
putchar(65 + k);
}
puts(".");
}
return 0;
}
```
by L2_sheep @ 2018-11-29 15:56:45
那题洛谷里也有,是P1347
by L2_sheep @ 2018-11-29 18:09:30