poj 1094 Sorting It All Out

思路：题目的意思就是说每输入一个关系，进行一次拓扑排序，知道能够确定n个字母的顺序

 或者是存在环。在编写程序时首先要判断是不是有环，如果有，返回0，

 如果存在多种情况，标记flag2为-1，然后继续进行判断有没有环，如果没有，返回-1；

 如果没没出现上述情况，则返回1。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 int n,m,j,i;
 4 int map[100][100],q,d[100],t[100];
 5 int flag,flag1;
 6 char a[100];
 7 int ju[100];
 8 int topo()
 9 {  
10     int i,j,flag2=1,p,temp,k=0;  
11     for(i=0;i<n;i++)   
12         t[i]=d[i];   
13     for(i=0;i<n;i++)   
14     {       p=0;       
15     for(j=0;j<n;j++)        
16         if(t[j]==0)      
17         {          
18             p++;        
19         temp=j;      
20         }       
21         if(p==0&&p!=n)    
22             return 0;       
23         if(p>1)     
24             flag2=-1;  
25         ju[k++]=temp;      
26         t[temp]=-1;      
27         for(j=0;j<n;j++)      
28             
29             if(map[temp][j]==1)           
30                 t[j]--;  
31     }   return flag2;
32 }
33 int main()
34 {  
35     while(1)
36     {    
37         scanf("%d %d",&n,&m);  
38         flag1=0;    
39         if(n==0&&m==0)
40             break;   
41         memset(map,0,sizeof(map));
42         memset(d,0,sizeof(d));   
43         for(i=0;i<m;i++)    
44         {       
45             scanf("%s",a);      
46             map[a[0]-'A'][a[2]-'A']=1;      
47             d[a[2]-'A']++;        
48             if(flag1==0)         
49                 q=topo();       
50             if(q==1&&flag1==0)       
51             {          
52                 printf("Sorted sequence determined after %d relations: ",i+1);  
53                 for(j=0;j<n;j++)           
54                     printf("%c",ju[j]+'A');      
55                 printf(".\n");          
56                 flag1=1;      
57                 
58             }        
59             if(q==0&&flag1==0)       
60             {           
61                 printf("Inconsistency found after %d relations.\n",i+1);   
62                 flag1=1;       
63             }    
64         }      
65         if(flag1==0)     
66             printf("Sorted sequence cannot be determined.\n");
67     }    
68     return 0;
69 }