首页 > 代码库 > 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;
}