HDU 1285 确定比赛名次。

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1285
纯粹的拓扑排序
View Code
 1 #include <stdio.h>
 2 #include <string.h>
 3 int count,n,in[505],map[505][505],vis[505],sort[505];
 4 
 5 void topo(int x)
 6 {
 7     vis[x] = 1;
 8     sort[count] = x;
 9     count++;
10     int i;
11     for(i = 1;i <= n;i++)
12     {
13         if(map[x][i] && !vis[i])//只对未访问过的临界点有效~
14         in[i]--;
15     }
16 }
17 
18 int main()
19 {
20     int a,b,m,i,j;
21     while(~scanf("%d %d",&n,&m))
22     {
23         memset(map,0,sizeof(map));
24         memset(in,0,sizeof(in));
25         memset(vis,0,sizeof(vis));
26         for(i = 0;i < m;i++)
27         {
28             scanf("%d %d",&a,&b);
29             if(map[a][b] == 0)
30             map[a][b] = 1,in[b]++;
31         }
32         count = 0;
33         while(count < n)
34         {
35             for(i = 1;i <= n;i++)
36             {
37                 if(!vis[i] && !in[i])//没有访问过且in为零
38                 {
39                     topo(i);
40                     break;
41                 }
42             }
43         }
44         for(i = 0;i < n-1;i++)
45         printf("%d ",sort[i]);
46         printf("%d\n",sort[i]);
47     }
48 }