HDU 4857脱出【トポロジーソート+リバースビルディング+優先キュー】

から逃げる
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 5   Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
悪いことが起こったので,今ではみんな忙しくて逃げている.しかし逃げ道は狭く、みんな1列に並ぶしかありません.
現在n人います.1番からnまでです.同時にいくつかの奇妙な制約条件があり、それぞれはaがbの前に形成されなければならない.
同時に、社会は不平等で、これらの人は貧乏で豊かです.1番が一番金持ちで、2番が二番目に金持ちで、このように押します.金持ちは責任者に賄賂を渡したので、彼らにはいくつかのメリットがある.
担当者は今、みんなが並んでいる順番を手配することができます.メリットが得られたので、1番をできるだけ前にして、この時にいろいろな状況があれば、2番をできるだけ前にして、いろいろな状況があれば、3番をできるだけ前にして、このようにします.
では、みんなの順番を手配しなければなりません.私たちは必ず解があることを保証します.
Input
1行目の整数T(1<=T<=5)は、テストデータの個数を表す.
次に、各テストデータについて、最初の行には、人数および制約の個数をそれぞれ表す2つの整数n(1<=n<=30000)およびm(1<=m<=100000)がある.
次に、m行、各行の2つの整数aおよびbは、制約a番号がb番号の前にあることを示す.aとbは必ず違う.
Output
各テストデータに対して、1行のキューの順序を出力し、スペースで区切ります.
Sample Input

1
5 10
3 5
1 4
2 5
1 2
3 4
1 4
2 3
1 5
3 5
1 2

Sample Output

1 2 3 4 5

/*  問題解:リバースビルド+優先キューリバースビルド後、最大値優先優先優先優先の優先キューでトポロジーソートすることで、可能な場合、まず最大を選択し、最小を最終選択*/

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define maxn 30002
int n,m,iq,in[maxn],ans[maxn];
using namespace std;

struct cmp{
	bool operator()(int &a,int &b)
	{
	return a<b;//    
	}
};

vector <int> e[maxn];

void topo()
{
	priority_queue<int,vector<int>,cmp> q;//    ,     
	for(int i=1; i<=n; i++)
	{
		if(in[i]==0) q.push(i);
	}
	while(!q.empty())
	{
		int x=q.top();
		q.pop();
		ans[iq++]=x;//ans        
		for(int i=0; i<e[x].size(); i++)
		{
			in[e[x][i]]--;
			if(in[e[x][i]]==0) q.push(e[x][i]);
		}
	}
}

int main()
{
	int T,a,b;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
		for(int i=0; i<=n; i++) e[i].clear();//   
		while(m--)
		{
			scanf("%d %d",&a,&b);
			e[b].push_back(a);//   ，    
			in[a]++;
		}
		iq=1;
		topo();
		printf("%d",ans[iq-1]);
		for(i=iq-2; i>=1; i--) printf(" %d",ans[i]);
		printf("
");
	}
	return 0;
}