首页 > 代码库 > hdu 1285 确定比赛名次 拓扑排序

hdu 1285 确定比赛名次 拓扑排序

第一道拓扑排序题。。

拓扑排序就是一个有向图,如果这个图有环就不能用拓扑排序。

对于拓扑排序就是将没有进只有出的点或别的先出。。出来后将原来图中与输出有关的线全部删除,直到找不到这要的点或数据。。

注意对重边的处理

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int s[505][505];
int a,b;
int w[1000];
int yy[505];
int main()
{
    int n,m;
   while(~scanf("%d %d",&a,&b))
   {
       memset(s,0,sizeof(s));
       memset(w,0,sizeof(w));
       for(int i=0;i<b;i++)
       {
           scanf("%d %d",&n,&m);
           if(s[n][m]==0)
            {s[n][m]=1;
           w[m]++;}
       }
       int ans=0;
       for(int i=1;i<=a;i++)
       {
           for(int j=1;j<=a;j++)
           { //printf("%d\n",w[1]);
               if(w[j]==0)
               {//printf("%d\n",j);
                   yy[ans++]=j;
                   w[j]=-1;
                   for(int kk=1;kk<=a;kk++)
                    {//printf("%d\n",kk);
                        if(s[j][kk]==1)
                         w[kk]--;}
                    break;
               }
           }
       }
       printf("%d",yy[0]);
       for(int i=1;i<ans;i++)
          printf(" %d",yy[i]);
        printf("\n");
   }
   return 0;
}