HDU1285+拓扑排序

注意重边！！！！
View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn = 505;
 9 int mat[ maxn ][ maxn ];
10 int ind[ maxn ];
11 int res[ maxn ];
12 int vis[ maxn ];
13 
14 void init(){
15     memset( vis,0,sizeof( vis ) );
16     memset( ind,0,sizeof( ind ) );
17     memset( mat,0,sizeof( mat ) );
18 }
19 
20 void topo( int n ){
21     int cnt = 0;
22     for( int i=1;i<=n;i++ ){
23         int start=-1;
24         for( int j=1;j<=n;j++ ){
25             if( ind[ j ]==0&&vis[j]==0 ){
26                 start = j;
27                 vis[ j ] = 1;//表示已经剔除该点
28                 break;
29             }
30         }
31         if( start!=-1 ) res[ cnt++ ] = start;
32         else break;
33         for( int j=1;j<=n;j++ ){
34             if( mat[start][j]==1 ){
35                 ind[ j ]--;
36             }
37         }
38     }
39     return ;
40 }//比较暴力的拓扑排序
41 
42 void output( int n ){
43     for( int i=0;i<n;i++ ){
44         if( i==0 ) printf("%d",res[i]);
45         else printf(" %d",res[i]);
46     }
47     printf("\n");
48 }
49         
50 int main(){
51     int n,m;
52     while( scanf("%d%d",&n,&m)==2 ){
53         init();
54         int a,b;
55         while( m-- ){
56             scanf("%d%d",&a,&b);
57             if( mat[a][b]==0 ){
58                 mat[a][b]=1;
59                 ind[ b ]++;
60             }
61         }
62         topo( n );
63         output( n );
64     }
65     return 0;
66 }
由于n比较小，可以暴力。
keep moving...