HDU 1285 确定比赛名次

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1285

图论最简单的拓扑排序寻找入度为0的点删掉然后让跟它相连的点入度减一

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int map[501][501],topp[501],inde[501];
 5 void toppsort(int n)
 6 {
 7     int i,j,k;
 8     for(i=1;i<=n;i++)
 9     {
10         for(j=1;j<=n;j++)
11         {
12             if(inde[j]==0)
13             {
14                 inde[j]--;
15                 topp[i]=j;
16                 for(k=1;k<=n;k++)
17                 {
18                     if(map[j][k])
19                     inde[k]--;
20                 }break;
21 
22             }
23         }
24     }
25 }
26 int main()
27 {
28   int n,m,i,j,a,b;
29   while(scanf("%d%d",&n,&m)!=EOF)
30   {
31       memset(map,0,sizeof(map));
32       memset(inde,0,sizeof(inde));
33       for(i=1;i<=m;i++)
34       {
35           scanf("%d%d",&a,&b);
36           if(!map[a][b])
37           {
38              map[a][b]=1;
39              inde[b]++;
40           }
41       }
42       toppsort(n);
43       for(i=1;i<n;i++)
44       {
45           printf("%d ",topp[i]);
46       }
47       printf("%d\n",topp[n]);
48   }
49   return 0;
50 }