【题意】

有N 个不同重量的球，重量为1～N 个单位。

对球从1到N 进行标记，使得： ①没有两个球具有相同的标签；②标签满足几个约束，例如“标签为a 的球比标签为b 的球轻”。

【输入输出】

输入：

第1行包含测试用例的数量。每个测试用例的第1行都包含两个整数N （1≤N ≤200）和M （0≤M ≤40000），分别表示球的数量和约束的数量。后面的M 行，每行都包含两个整数a 和b ，表示标签为a 的球比标签为b 的球轻（1≤a ,b ≤N ）。

在每个测试用例前都有一个空行。

输出：

对于每个测试用例，都单行输出标签1～N 的球的重量。如果存在多种解决方案，则输出标签为1的球的最小重量，然后输出标签为2的球的最小重量，以此类推……如果不存在解，则输出-1。

【思路分析】

这道题不是输出小球的标签，而是按照标签输出小球的重量，而且标签小的球的重量尽可能小。

举个栗子：

输入以下数据，

5 4 //节点数 5 1 //标签为5 的球比标签为1 的球轻 4 2 1 3 2 3 1 2 3 4 5

根据重量关系，节点3 是最重的。因此令重量weight[3]=5；节点1和节点2比节点3轻，因为每个球的重量都不同，按照标签小的球重量小的原则，先给标签大的球分配重量，先处理节点2，因此weight[2]=4；节点4比节点2轻，weight[4]=3；节点1比节点3轻，weight[1]=2；节点5比节点1轻，weight[5]=1。按照标签1～5输出其重量：2 4 5 3 1。

例如，输入以下数据

10 5 //节点数、边数 4 1 //标签为4 的球比标签为1 的球轻 8 1 7 8 4 1 2 8 1 2 3 4 5 6

按照标签小的球重量小的原则，先给标签大的球分配重量：weight[10]=10；weight[9]=9；weight[6]=8；weight[5]=7；weight[3]=6；weight[1]=5。节点8和节点4比节点1轻，按照标签小的球重量小的原则，先给标签大的球分配重量，先处理节点8，因此weight[8]=4；节点7和节点2比节点8轻，先处理节点7，weight[7]=3；现在只剩下节点4和节点2，weight[4]=2；weight[2]=1。

按照标签1～10输出其重量：5 1 6 2 7 8 3 4 9 10。

这道题有重复边，需要去重，否则会有环，最后输出-1

【算法设计】

方法1：建立正向图。i =n …1，j =n …1，检查第1个出度为0的点t ，分配重量w [t ]=i ，将弧尾节点的出度减1，继续下一个循环。若没有出度为0的节点，则说明有环，退出。 方法2：建立原图的逆向图。i =n …1，j =n …1，检查第1个入度为0的节点t ，分配重量w [t ]=i ，将其邻接点的入度减1，继续下一个循环。若没有入度为0的节点，则说明有环，退出。

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;
const int maxn = 210;
int map[maxn][maxn], in[maxn] , w[maxn];

int n , m , T, u ,v;
bool flag;

void TopoSort(){ //拓扑排序 
	
	flag = 0;
	for(int i = n ; i > 0 ; i --){
		
		int t = -1;
		for(int j = n ; j > 0 ; j--){
			
			if(!in[j]){
				
				t = j;
				break;
			}
		}
		if(t == -1){ //有环 
			
			flag = 1;
			return;
		}
		
		in[t] = -1;
		w[t] = i;
		for(int j = 1 ; j <= n ; j ++){
			
			if(map[t][j]){
				in[j] --;
			}
		}
	}
} 

int main(){
	
	cin >> T;
	
	while(T--){
		
		memset(map , 0 ,sizeof(map));
		memset(in , 0 , sizeof(in));
		
		cin >> n >> m;
		for(int i = 1; i <= m ; i++){
			
			cin >> u >> v;
			if(!map[v][u]){ //建立逆向图，检查重复边 
				
				map[v][u] = 1;
				in[u] ++;
			}
		}
		TopoSort();
		if(flag){
			cout << -1 << endl;
			continue;
		}
		
		for(int i = 1; i < n ; i++){
			
			cout << w[i] << " ";
		}
		cout << w[n] << endl;
	}
	return 0;
}