题目分的三种情况 不能有环出现
判断环的时候在处理输入的时候判断 另外还在处理完后有一个三重循环的判断
这个代码是参考过别人的 最近没怎么做 手很生···
#include <iostream>
using namespace std;
int sorted[27];
int map[27][27];
char str[200][4];
int main()
{
int n,m;
int t;
int i,j,k;
L2:
while(scanf("%d%d",&n,&m)==2 && n &&m)
{
for(t=1;t<=m;t++)
scanf("%s",str[t]);
memset(map,0,sizeof(map));
for(t=1;t<=m;t++)
{
i=str[t][0]-'A'+ 1;
j = str[t][2]-'A'+ 1;
switch(str[t][1])
{
case '>':
if(map[i][j] == -1 || map[j][i] == 1)
goto RESTRIC;
map[i][j] = 1;
map[j][i] = -1;
break;
case '<':
if(map[i][j] == 1 || map[j][i] == -1)
goto RESTRIC;
map[i][j] = -1;
map[j][i] = 1;
break;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(map[i][k] && map[k][j] && k!=i && i!=j )
{
if(!map[i][j])
{
if(map[i][k] == map[k][j])
{
map[i][j] = map[i][k];
map[j][i] = -map[i][k];
}
}
else
{
if(map[i][k] == map[k][j])
{
if(map[i][k] != map[i][j])
goto RESTRIC;
}
}
}
}
for(i=1;i<=n;i++)
{
int p = 1;
for(j=1;j<=n;j++)
{
if(i!=j)
{
if(map[i][j] == 0)
goto L;
if(map[i][j] == 1)
p++;
}
}
sorted[p] = i;
}
printf("Sorted sequence determined after %d relations: ",t);
for(i=1;i<=n;i++)
putchar(sorted[i]+'A'-1);
printf(".\n");
goto L2;
L:
;
}
printf("Sorted sequence cannot be determined.\n");
continue;
RESTRIC:
printf("Inconsistency found after %d relations.\n",t);
}
return 0;
}