題目分的三種情況 不能有環出現
判斷環的時候在處理輸入的時候判斷 另外還在處理完后有一個三重循環的判斷
這個代碼是參考過別人的 最近沒怎么做 手很生···
#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;
}