这道题一开始什么思路都没有,最后还是看了标签;
然后经过大神的一句话;
判断是否会连成环;
这道题判断最好用floyd;
因为好写;
一旦出现环,自然是矛盾,输出,然后exit(0);
如果没有环,就深搜一边;
如果可以把所以有的点都遍历到;
就直接输出成立;
否则;
如果所有的都输入完了,还是不能判断;
就输出无法判断;
还有一点就是每输入一次就判断一次,即做一遍以上步骤;
最好dfs时用vector或者链式前向星加速,不然第九个点会TLE;
以及成立的时候输出的东西后有个句点;
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define C char
#define R register
#define IL inline
#define I 30
using namespace std;
struct node {
II to,up;
}aa[I];
II head[I*123];
II _tot;
void add(R II x,R II y)
{
aa[++_tot].to=y;
aa[_tot].up=head[x];
head[x]=_tot;
}
II had[I], f[I][I], ans[I], in[I];
II n,m,now;
IL II can()
{
for(R II i=1;i<=26;i++)
{
for(R II j=1;j<=26;j++)
{
for(R II k=1;k<=26;k++)
{
f[j][k]=max(f[j][k],f[j][i]&f[i][k]);
}
}
}
for(R II i=1;i<=26;i++) if(f[i][i]) return 0;
return 1;
}
IL II dfs(R II x,R II ka)
{
ans[ka]=x;
if(ka==n) return 1;
for(R II i=head[x];i;i=aa[i].up)
{
II g=aa[i].to;
if(!had[g]) {
had[g]=1;
if(dfs(g,ka+1)) return 1;
had[g]=0;
}
}
return 0;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for(R II i=1;i<=m;i++)
{
R C a,b,z;
cin>>a>>z>>b;
R II ka1=a-'A'+1;
R II ka2=b-'A'+1;
f[ka1][ka2]=1;
add(ka1,ka2);
in[ka2]++;
if(!can()) {
printf("Inconsistency found after %d relations.\n",i);
exit(0);
} else {
for(R II j=1;j<=26;j++)
{
if(!in[j]) {
for(R II k=1;k<=26;k++) had[k]=0;
if(dfs(j,1)) {
printf("Sorted sequence determined after %d relations: ",i);
for(R II k=1;k<=n;k++) printf("%c",ans[k]-1+'A');
cout<<'.'<<endl;
exit(0);
}
}
}
}
}
printf("Sorted sequence cannot be determined.\n");
exit(0);
}
```