hdu 3342 Legal or Not <拓扑排序>

链接 http://acm.hdu.edu.cn/showproblem.php?pid=3342

题意：拓扑排序判断是否成环。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 int map[501][501], v[501], in[501], M, N;
 4 void Init( )
 5 {
 6     memset( map, 0, sizeof map );
 7     memset( in, 0, sizeof in );
 8     memset( v, 0, sizeof v );
 9     int a, b;
10     for(int i=0; i<M; ++ i  ){
11         scanf("%d%d", &a, &b);
12         if(!map[a][b]){  //判断是否重边 
13             map[a][b]=1;
14             in[b]++;   //入度 +1 
15         }
16     }
17 }
18 int  Topsort(int top )
19 {
20     int i, j, k;
21     for( i=0; i<N; ++ i ){
22         for(  j=0; j<N; ++ j ){
23             if( !v[j]&&in[j]==0 )break;
24         }
25         if( j==N ){
26             return 0;// i<N 还有没有找到的点  j>=N，没有入度为0的点了 
27         }
28         else{
29             v[j]=1;
30             for( k=0; k<N;++k ){
31                 if(map[j][k] && in[k])
32                     in[k]--;
33             }
34         }
35     }
36     return 1;
37     
38 }
39 int main( )
40 {
41     while(scanf( "%d%d", &N, &M ) ==2,M+N ){
42         Init( );
43         int f=Topsort(1);
44         if( f )puts( "YES" );
45         else puts( "NO");    
46     }
47     return 0;
48 }