首页 > 技术文章 > poj 3687(拓扑排序)

jaszzz 2020-05-13 21:32 原文

题意:有一些球他们都有各自的重量,而且每个球的重量都不相同,现在,要给这些球贴标签。如果这些球没有限定条件说是哪个比哪个轻的话,那么默认的前面比后的要请,而且这n个球的重量也正好是分布在1-n这个范围内,现在要你求出他们各自所占的重量。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 210;

int dig[MAX_N];
int judge[MAX_N][MAX_N];
int loc[MAX_N];
int m,n;

priority_queue<int> s;

int topsort()
{
	int num=n;
	for(int i=1;i<=n;i++)
		if(!dig[i])	s.push(i);
	if(s.empty())	return 0;
	while(!s.empty())
	{
		int tmp=s.top(); s.pop();
		loc[tmp]=num--;
		for(int i=1;i<=n;i++)
		{
			if(judge[i][tmp])
			{
				judge[i][tmp]=0;
				dig[i]--;
				if(!dig[i])	s.push(i);
			}
		}
	}
	if(num!=0)	return 0;
	return 1;
}

int main(void)
{
	int t,a,b;
	scanf("%d",&t);
	while(t--)
	{
		memset(dig,0,sizeof(dig));
		memset( judge,0,sizeof( judge));
        memset( loc,0,sizeof(loc));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			if(judge[a][b]>0)	continue;
			judge[a][b]=1;
			dig[a]++;
		}
		a=topsort();

		if(a)
		{
			int i=1;
			for( ; i < n ; printf("%d ",loc[ i++ ]) );
            printf("%d\n",loc[ i ]);
		}
		else
		{
			printf("-1\n");
		}
		
	}
	return 0;
}

  

推荐阅读