UVA-10305-Ordering Tasks

小小的香辛料

于 2018-08-08 17:27:01 发布

阅读量209

点赞数

分类专栏： ACM划水体验

本文链接：https://blog.csdn.net/doubleguy/article/details/81512110

版权

ACM划水体验专栏收录该内容

59 篇文章

订阅专栏

本文深入探讨了拓扑排序算法的应用，通过一个实例演示了如何使用该算法解决特定问题。强调了拓扑排序结果的多样性和正确性的判断标准，即只要遵循拓扑排序原则，输出的序列就是有效的解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

这道题没有什么技术含量，一个拓扑排序就行了，这里我写这道题的目的是要让我们注意到他排序之后有很多种情况，如果题目没有要求（通常都有规定的顺序），那么只要是拓扑排序过的任意一种序列都是对的（即使你的程序跑出来的结果和样例不一样也是对的）。

AC代码如下：

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n,m;
int a[105][105];
int vis[10005];
void toposort()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!vis[j])
			{
				vis[j]--;
				printf("%d",j);
				if(i!=n)	printf(" ");
				else 		printf("\n");
				for(int k=1;k<=n;k++)
				{
					if(a[j][k])	vis[k]--;
				}
				break;
			}
		}
	}
}

int main()
{
	int p,q;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(a,0,sizeof(a));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&p,&q);
			if(!a[p][q])	
			{
				a[p][q]=1;
				vis[q]++;
			}
		}
		toposort();	
	}
	return 0;
}