拓扑排序

poj 1094 Sorting It All Out http://poj.org/problem?id=1094

【题意】：给出n个点 m对大小关系求输入第几对关系的时候可以把整个图n个点的大小关系确定或出现环一旦发现出现了环或确定下了大小关系后面的都不用管了做法是：每进去一条边就判断一次一发现都上述两种情况就可以输出了

 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(".
");
83                 }
84                 if(ans==2)                    
85                     printf("Inconsistency found after %d relations.
",i);                
86                 break;
87             }
88         }
89         if(i>m)
90             printf("Sorted sequence cannot be determined.
");
91     }
92     return 0;
93 }