HDU 1285 确定比赛名次【拓扑排序】

浏览数：22 / 时间：2015年06月08日

题意：中文的题目-----这道题让我终于明白了那个break的作用---因为题目中有这一句“符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前”@_@

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;
int map[505][505],indegree[505],queue[505];
int main()
{
	int n,m,i,j,k,a,b,iq;
	while(scanf("%d %d",&n,&m)!=EOF&&n&&m)
	{
		memset(map,0,sizeof(map));
		memset(indegree,0,sizeof(indegree));
		for(i=1;i<=m;i++)
		{
			scanf("%d %d",&a,&b);
			if(!map[a][b])
			{
				map[a][b]=1;
				indegree[b]++;
			}
		}
		iq=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(indegree[j]==0)
				{
					indegree[j]--;
					queue[iq++]=j;
					break; //每次只扫一次，这样保证了题目中说的"符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前" 
				}				
			}
			
			for(k=1;k<=n;k++)
			{
				if(map[j][k]) indegree[k]--;
				
			}
		}
		
		for(i=0;i<iq-1;i++)
		printf("%d ",queue[i]);
		printf("%d\n",queue[i]);
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。