[HDU] 1285 确定比赛名次(拓扑排序)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<stdbool.h>
 7 #include<time.h>
 8 #include<stdlib.h>
 9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<queue>
13 #include<vector>
14 using namespace std;
15 #define clr(x,y)    memset(x,y,sizeof(x))
16 #define sqr(x)      ((x)*(x))
17 #define rep(i,a,b)  for(int i=(a);i<=(b);i++)
18 #define LL          long long
19 #define INF         0x3f3f3f3f
20 #define A           first
21 #define B           second
22 
23 int cnt,num,n,m,head[600],d[600],a[600];
24 
25 struct node
26 {
27     int u,v,w;
28     int next;
29 } edge[10000];
30 
31 void init()
32 {
33     clr(head,-1);
34     clr(a,0);
35     clr(d,0);
36     cnt=0;
37     num=0;
38 }
39 
40 void add(int u,int v,int w)
41 {
42     edge[cnt].v=v;
43     edge[cnt].w=w;
44     edge[cnt].next=head[u];
45     head[u]=cnt++;
46 }
47 
48 void tops()
49 {
50     int u;
51     for(int i=0;i<n;i++) {
52         for(int j=1;j<=n;j++) {
53             if(!d[j]) {
54                 u=j;
55                 d[j]--;
56                 a[num++]=j;
57                 break;    
58             }
59         }
60         for(int j=head[u];j!=-1;j=edge[j].next) {
61             d[edge[j].v]--;
62         }
63     }
64     
65     for(int i=0;i<num;i++) {
66         if(i!=num-1) printf("%d ",a[i]);
67         else         printf("%d\n",a[i]);
68     }
69 }
70 
71 int main()
72 {
73     int x,y;
74     
75     while(~scanf("%d%d",&n,&m)) {
76         init();
77         while(m--){
78             scanf("%d%d",&x,&y);
79             add(x,y,1);
80             d[y]++;
81         }
82        
83         tops();
84     }
85     
86     return 0;
87 }