1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 int g[100][100],ss[100],n,m,degree[100],uu[1000],vv[1000],temp[100];
 5 
 6 
 7 int solve()
 8 {
 9     queue<int > q;
10     int i,j,num,k;
11     k=0;
12     num=0;
13     for(i=0;i<n;i++)                
14         temp[i]=degree[i];    
15     for(i=0;i<n;i++)
16         if(temp[i]==0)
17         {
18             q.push (i);
19             num++;
20             if(num>1)
21                 k=1;            
22         }
23         int nn=0;
24         while(!q.empty ())
25         {
26             int t=q.front ();q.pop ();ss[nn++]=t;
27             num=0;
28             for(i=0;i<n;i++)
29                 if(g[t][i]==1)
30                 {
31                     temp[i]--;
32                     if(temp[i]==0)
33                     {
34                         q.push (i);
35                         num++;
36                         if(num>1)   //用拓扑排序 删点过程中出现不止一个入度为0（这几个入度为0的点之间的大小不能确定）
37                             k=1;
38                     }
39                 }
40         }        
41         if(nn<n)
42             return 2;
43         else
44         {
45             if(k==0)
46                 return 1;
47             return 0;
48         }
49 }
50 
51 int main()
52 {
53     int i,j;
54     char u,v,h;
55     while(scanf("%d%d",&n,&m))
56     {
57         if(n==0&&m==0)
58             break;
59         for(i=1;i<=m;i++)
60         {
61             getchar();
62             scanf("%c%c%c",&u,&h,&v);
63             uu[i]=u-'A';  vv[i]=v-'A';
64         }
65         memset(g,0,sizeof(g));
66         memset(degree,0,sizeof(degree));
67         for(i=1;i<=m;i++)
68         {
69             if(g[uu[i]][vv[i]]==0)
70             {
71                 g[uu[i]][vv[i]]=1;
72                 degree[vv[i]]++;//入度 
73             }            
74             int ans=solve();       //0是没排好序 1排好了 2有环
75             if(ans!=0)
76             {
77                 if(ans==1)
78                 {
79                     printf("Sorted sequence determined after %d relations: ",i);
80                     for(j=0;j<n;j++)
81                         printf("%c",ss[j]+'A');
82                     printf(".\n");
83                 }
84                 if(ans==2)                    
85                     printf("Inconsistency found after %d relations.\n",i);                
86                 break;
87             }
88         }
89         if(i>m)
90             printf("Sorted sequence cannot be determined.\n");
91     }
92     return 0;
93 }

优质内容筛选与推荐>>
1、ORA-01747: user.table.column, table.column 或列说明无效
2、vue.js计算属性 vs methods
3、一个留美女博士的七年----分享给所有还相信梦想的朋友
4、17-7-24-react入门
5、Ajax入门(一)