9度OJ 教程81 拓扑排序——确立比赛名次

九度OJ 教程81 拓扑排序——确立比赛名次

九度题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=80

免费题目地址：http://acmclub.com/problem.php?id=1077

//九度OJ 教程81 拓扑排序之确立比赛名次
//http://ac.jobdu.com/problem.php?cid=1040&pid=80
//有向图利用存储矩阵存储，另设一个标记数组flag[]表示已经被删除的节点。
#include <stdio.h>
#include<string.h>
#define MAXS 502
int main()
{
	int n,m,i,j,k,mark[MAXS][MAXS]={0},flag[MAXS];
	while(~scanf("%d %d",&n,&m))
	{
		memset(mark,0,MAXS*MAXS*sizeof(int));
		memset(flag,1,MAXS*sizeof(int));//设置未访问标志。
		while(m--)
		{
			scanf("%d %d",&i,&j);
			if(mark[i][j])continue;//防止变态的case给重复输入某个结果……
			mark[i][j]=1;
			mark[0][j]++;//0行j列存储入度数，即选手j被击败的次数。
		}
		for(j=1;j<n;j++)//纯粹为了执行n-1次，没其他意思。取出前n-1名，最后一名单独处理，要加\n的。
		{
			for(k=1;k<=n;k++)
			{
				if(flag[k]&&(mark[0][k]==0))
				{
					flag[k]=0;//设置移除标志
					break;//结束循环。
				}
			}
			printf("%d ",k);
			for(i=1;i<=n;i++)//把该点从图中去除。
			{
				if(mark[k][i])
				{
					mark[k][i]=0;
					mark[0][i]--;//被击败数减一。
				}
			}
		}
		for(k=1;k<=n;k++)
		{
			if(flag[k]&&(mark[0][k]==0))
			{
				flag[k]=0;
				break;
			}
		}
		printf("%d\n",k);
	}
	return 0;
}