sdnu 1257.Problem E. SDNU ACM/ICPC TEAM 反向topo排序

1257.Problem E. SDNU ACM/ICPC TEAM

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 9 Accepted Submission(s): 4

Description

Lulichuan is the captain of SDNU ACM/ICPC TEAM, he have many team members, Their ability has a sequence from 1 to N, now , lulichuan want to labeled them from 1 to N in this way

a. Two member have different label

b. The labeling satisfies several constrains like "The member labeled with x is lower than the one labeled with y”.

Input

The first line is T, T is TestCase(0 < T <= 1000)

The first line of each testcase is two number N, M(0 < 500 < n, 0 < M < 100000)

The next M line each contain two integers x and y indicating the member labeled with x must be lower than the one labeled with y. (1 ≤ x, y ≤ N)

Output

For each test case output on a single line the member' ability from label 1 to label N. If several solutions exist, you should output the one with the lowest ability for label 1, then with the lowest ability for label 2 and so on... If no solution exists, output -1 instead.

Sample Input

54 04 11 14 21 22 14 12 14 13 2

Sample Output

1 2 3 4-1-12 1 3 41 3 2 4

这道题的大体意思：：陆厉川这个zz要给队员打标记~~一共n个人，分别拥有着1~n的能力值，打标记的话~一个是由m个要求：：第x个的能力一定要比y弱！！，另一个是在满足上个的情况下从1开始~尽量让他们拥有他们能拥有的最小能力值~，

意思就是先让1的能取到的最小能力值不论方法先取到~再是从2开始。。。以此类推。

这道题一共有两个注意的地方~一个是需要用到反向topo排序：：因为决定排序的一个原因是最后的比较的最强能力者决定~~就比如如果有条件3一定要比2弱~~那么决定排列先后的是2而不是3。

还有就是~按照要求排列出来后，得出来的结果：：其实是每个能力者对应的序号~~就像是把序号按要求排列后~从1到n赋给能力者~~但是注意的是~他最后要求的是按照序号来输出能力~__~ 很烦~。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<functional>
#include<cstring>
using namespace std;
priority_queue<int>q;
vector<int>ma[100005];
int out[100005];
int ans1[100005];
int ans[100005];
int cnt = 1;
int m, n;
void topo()
{
	for (int s = 1; s <= m; s++)
	{
		if (out[s] == 0)
		{
			q.push(s);
			//	cout << s << endl;
		}
	}
	while (!q.empty())
	{
		int t = q.top();
		q.pop();	 
	//	cout << cnt<<" "<<t << endl;
		ans1[t] = cnt;//这是序号对应能力
		ans[cnt--] = t;//这是能力对应序号
		for (int s = 0; s < ma[t].size(); s++)
		{
			out[ma[t][s]]--;
			if (out[ma[t][s]] == 0)
			{
				q.push(ma[t][s]);
			}
		}
	}
}
int main()
{
	int te;
	scanf("%d", &te);
	while (te--)
	{
		memset(out, 0, sizeof(out));
		scanf("%d%d", &m, &n);
		cnt = m;
		for (int s = 1; s <= m; s++)
		{
			ma[s].clear();
		}
		while (n--)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			ma[b].push_back(a);
			out[a]++;
		}
		topo();
		
		if (cnt !=  0)
		{
			cout << "-1" << endl;
		}
		else
		{
			for (int s = 1; s<m; s++)
			{
				printf("%d ", ans1[s]);
			}
			cout << ans1[m] << endl;
		}
	}
	return 0;
}