HDU1285 确定比赛名次(拓扑排序）

题目是要确定比赛名次，因为这个有先后次序，要按照次序输出，次序相同的情况下，按照编号小数字输出。

这道题目看懂了以后可以分析出是拓扑排序的模板题目。

需要处理的一点是，每次找入度为0的点，从编号小的地方开始找，这样输出的时候就是按照从小到大的顺序输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int n,m,a,b,flag;
int maps[505][505],deg[505],ans[505];
void TopSort()
{
    int i,j,x,k;
    k=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(deg[j]==0)
            {
                deg[j]--;
                ans[k++]=j;
                for(x=1;x<=n;x++)
                    if(maps[j][x])
                        deg[x]--;
                break;
            }
        }
        if(j>n)
        {
            flag=0;
            printf("存在回路\n");
            return;
        }
    }
}
int main()
{
    int i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        flag=1;
        memset(ans,0,sizeof(ans));
        memset(deg,0,sizeof(deg));
        memset(maps,0,sizeof(maps));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            if(!maps[a][b])
            {
                maps[a][b]=1;
                deg[b]++;
            }
        }
        TopSort();
        if(flag)
            for(i=1;i<=n;i++)
                if(i!=n)
                    printf("%d ",ans[i]);
                else
                    printf("%d\n",ans[i]);
    }
}