poj_3687 Labeling Balls

Labeling Balls

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 7681	Accepted: 2060

题目链接：http://poj.org/problem?id=3687

Description

Windy has N balls of distinct weights from 1unitto Nunits. Now he tries to label them with 1 to N in such away that:

1. No two balls share the same label. 

2. The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".

Can you help windy to find a solution?

Input

The first line of input is the number oftest case.The first line of each test case contains two integers, N (1 ≤ N≤ 200) and M (0 ≤ M ≤ 40,000). Thenext Mline eachcontain two integers a and b indicating the ball labeled with amust be lighter than the one labeledwith b. (1≤ a, b ≤ N)There is a blankline before each test case.

Output

For each test case output on a single linethe balls'weights from label 1 to label N. If several solutions exist, youshouldoutput the one with the smallest weight for label 1, then with thesmallestweight for label 2, then with the smallest weight for label 3 and soon... Ifno solution exists, output -1 instead.

Sample Input

5

4 0

4 1

1 1

4 2

1 2

2 1

4 1

2 1

4 1

3 2

Sample Output

1 2 3 4

-1

-1

2 1 3 4

1 3 2 4

Source

POJFounder MonthlyContest – 2008.08.31, windy7926778

题目大意：

输入T个测试案例，接下来输入N个点，M条边，接下来M行输入每条边的起点和终点，如果边产生回路，那么输出-1，否则按照输入的a轻于b，剩下的值就按从大到小输出。

解题思路：

将输入的n行建立有向图，如果该图产生回路，那么输出-1，如果不产生回路，将入度为0的点放进优先队列中，优先队列从大到小排序，每个队列按顺序出队，当出队的数与其他点有边存在，就在相应该点的入度减一，然后在判断是否入度为0，如果为0再次入队。本题一个比较容易出错的就是判重，如果输入两个相同的a和b，那么如果没有判重将会输出0，判重就在输入边时判断该边是否已经存在，如果存在该边的入度就不在自加。

/*

两组比较好的测试案例：

第二个测试案例有5个，但是有2个一样的，所以按4个算

2

54

51

42

13

23

105

41

81

78

41

28

ans:

24 5 3 1 逆向建图

51 6 2 7 8 3 4 9 10 没有判重边的话就输出 -1

*/

代码：

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>

using namespace std;

int g[210][210];
int degree[210];//入度
int value[210];
priority_queue<int> q;//定义优先队列

//得到入度为0的点
int toposort(int n)
{
	int j=n;
	for(int i=1;i<=n;i++)
	{
		if(degree[i]==0)
		{
			q.push(i);
		}
	}
	if(q.empty())
		return 0;
	while(!q.empty())
	{
		int t = q.top();
		q.pop();
		value[t]=j;
		j--;
		for(int i=1;i<=n;i++)
		{
			if(g[i][t]!=0)
			{
				g[i][t]=0;
				degree[i]--;
				if(degree[i]==0)
				{
					q.push(i);
				}
			}
		}
	}
	if(j!=0)
		return 0;
	return 1;
}

int main()
{
	int T;
	int n,m;
	int a,b;
	scanf("%d",&T);
	while(T--)
	{
		memset(g,0,sizeof(g));
		memset(degree,0,sizeof(degree));
		scanf("%d%d",&n,&m);
		while(m--)
		{
			scanf("%d%d",&a,&b);
			if(g[a][b]>0)//判重，如果输入一样的那么只算一个
                degree[a]--;
			g[a][b]=1;//a到b的边，起点a，终点b的边
			degree[a]++;
		}
		int x = toposort(n);
		if(x==0)
			printf("-1\n");
		else
		{
			for(int i=1;i<n;i++)
			{
				printf("%d ",value[i]);
			}
			printf("%d\n",value[n]);
		}

	}
	return 0;
}