思路主要就是Floyd传递闭包,但是数据1和数据9不管怎么调都至少有一个过不了,有巨佬帮忙调下吗,求求了
#include <bits/stdc++.h>
#define N 110
#define rint register int
using namespace std;
int n,m;
bool f[N][N];
bool vis[N][N];
bool b[N];
int ans;
int main()
{
scanf("%d%d",&n,&m);
for(rint i=1; i<=n; ++i) vis[i][i] = 1;
for(rint ii=1; ii<=m; ++ii)
{
string s;
cin>>s;
int u = s[0] - 'A' + 1,v = s[2] - 'A' + 1;
if((!f[u][v] && vis[u][v]) || (f[v][u]) || u == v)
{
return !printf("Inconsistency found after %d relations.",ii);
}
f[u][v] = 1;
f[s[0] - 'A' + 1][s[2] - 'A' + 1] = 1;
vis[s[0] - 'A' + 1][s[2] - 'A' + 1] = 1;
for(rint k=1; k<=n + 1; ++k)
for(rint i=1; i<=n + 1; ++i)
for(rint j=1; j<=n + 1; ++j)
if(f[i][k] && f[k][j])
{
if(!f[i][j] && vis[i][j])
return !printf("Inconsistency found after %d relations.",ii);
f[i][j] = 1,vis[i][j] = 1;
}
// for(rint i=1; i<=n; ++i)
// {
// for(rint j=1; j<=n; ++j)
// {
// printf("%d",f[i][j]);
// }
// printf("\n");
// }
// printf("\n");
// for(rint i=1;i<=n;++i)
// {
// for(rint j=1;j<=n;++j)
// {
// printf("%d",vis[i][j]);
// }
// printf("\n");
// }
for(rint i=1; i<=n + 1; ++i)
{
bool flag = 0;
for(rint j=1; j<=n + 1; ++j)
{
if(!f[i][j] && !f[j][i])
{
flag = 1;
break;
}
}
if(!flag) ++ans;
else break;
}
printf("%d\n",ans);
if(ans == n)
{
// for(rint i=1;i<=n;++i)
// {
// for(rint j=1;j<=n;++j)
// {
// printf("%d",f[i][j]);
// }
// printf("\n");
// }
// return 0;
printf("Sorted sequence determined after %d relations: ",ii);
memset(b,0,sizeof(b));
for(rint k=1; k<=n; ++k)
{
for(rint i=1; i<=n; ++i)
{
if(b[i]) continue;
bool flag = 0;
for(rint j=1; j<=n; ++j)
{
if(b[j] || i == j) continue;
if(!f[i][j] || f[j][i])
{
flag = 1;
break;
}
}
if(!flag)
{
b[i] = 1;
cout<<char(i + 'A' - 1);
break;
}
}
}
return !printf(".");
}
}
printf("Sorted sequence cannot be determined.");
return 0;
}