poj 3687 Labeling Balls(拓撲排序)

非常坑的一道題，最後快要繞暈了。。

題意：有N個球，重量分別是1~N，給著n個球貼上標簽。輸入n，m代表n個球和m條邊(a b)，代表 標簽為a的要比標簽為b的輕。最後輸出標簽1~N對應的重量（注意是重量，而不是輕重關系），還有要注意“ you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... ”,意思是標簽小的要盡可能貼在重量小的球上。

思路：因為標簽小的要盡可能貼在重量小的球上，所以拓撲排序時要使標簽小的盡可能的靠前。所以只是傳統的拓撲排序每次取優先隊列中入度為0並且數最小的不對的。因為即使該點最小，它後面連著的點未必是最小的。

例如上圖，若先取入度為0且最小的話，是先取出3，而我們的目的是讓標號小的盡量靠前，即應該讓1盡量靠前，這與先取出3相違背，這時應該先取出6才能使1盡量靠前。對於2,8，2肯定先出隊列。歸納起來便是對於若干平行的路徑，小的頭部不一定排在前面（如3），但大的尾部一定排在後面（如8）.

1. 把所有出度為 0 的節點放進優先隊列 PQ
2. WHILE： PQ 不是空隊列
3.     從 PQ 中取出編號最大的元素 a，把 a 添加到答案的頭部。
4.     FOR：所有指向 a 的邊 b → a
5.        把 b 的出度減 1。如果 b 的出度變為 0，則把 b 放進優先隊列 PQ。  

#include 
#include 
#include 
#include 
using namespace std;

int n,m;
int out[210];
int topo[210];
int map[210][210];
priority_queue < int, vector,less > que;

int toposort()
{
	while(!que.empty()) que.pop();
	int cnt = 1;
	memset(topo,0,sizeof(topo));
	for(int i = 1; i <= n; i++)
		if(out[i] == 0)
			que.push(i);

	while(!que.empty())
	{
		int u = que.top();	//每次取出隊列中最大的
		que.pop();
		topo[cnt++] = u;  
		for(int i = 1; i <= n; i++)
		{
			if(map[i][u] == 1)
			{
				out[i]--;
				if(out[i] == 0)
					que.push(i);
			}
		}
	}
	if(cnt == n+1)
		return 1;
	return 0;

}

int main()
{
	int test;
	scanf(%d,&test);
	while(test--)
	{
		scanf(%d %d,&n,&m);
		memset(out,0,sizeof(out));
		memset(map,0,sizeof(map));
		int flag = 1;

		for(int i = 0; i < m; i++)
		{
			int a,b;
			scanf(%d %d,&a,&b);
			if(!map[a][b])
			{
				map[a][b] = 1;
				out[a]++;
			}
			if(a == b)
				flag = 0;
		}
		if(!flag)
		{
			printf(-1
);
			continue;
		}
		int tmp[210];
		int ans = toposort();
		if(ans == 0)
			printf(-1
);
		else
		{
			for(int i = 1; i <= n; i++)
				tmp[ topo[i] ] = n+1-i;	//編號，tmp[]存的是拓撲排序的逆序.
			for(int i = 1; i <= n-1; i++)
				printf(%d ,tmp[i]); //輸出編號1~n對應的重量
			printf(%d
,tmp[n]);
		}

	}
	return 0;
}