F题解--“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛

F 考试成绩
拓扑排序，模板题。

代码：

#include<stdio.h>
#include<cstring>
const int Max=505;
int N,M;
int used[Max];//如果这个点当过起点，就删掉
int Map[Max][Max];//保存关系，也就是边
int in_degree[Max];//保存每个点的入度
int ans[Max];
void toposort()
{
    int cn=0;//一共要进行N个数的输出，所以我们需要
    while(cn<N)
    {
        int i,j;
        for(i=1;i<=N;i++)//寻找入度为0的点，起点
        {
            if(in_degree[i]==0&&used[i]==0)
            {
                   used[i]=1;//这个起点已经被用过了，就要去掉了,下次在找的话，就不会在用这个值了
                   break;//一旦找到立即跳出
            }
        }
        ans[cn]=i;//保留下第一个数
        for(j=1;j<=N;j++)//将以i为起点的所有的边全部删除
        {
            if(Map[i][j]==1)
            {
                Map[i][j]=0;
                in_degree[j]--;
            }
        }
        cn++;
    }
}

int main()
{

    while(~scanf("%d %d",&N,&M))
    {
        if(N==0&&M==0)break;
        memset(Map,0,sizeof(Map)),memset(used,0,sizeof(used)),memset(in_degree,0,sizeof(in_degree));
        for(int i=1;i<=M;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
      //去掉重边，因为两点最多就一个关系，重复输入的话,会导致入度加1，错误
            if(Map[a][b]==0)
            {
                Map[a][b]=1;//a-->b,a胜b
                in_degree[b]++;
            }
        }
        toposort();
        for(int i=0;i<N-1;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[N-1]);
    }
    return 0;
}