HDU 4857 탈출 [역방향 토폴로지 정렬] [우선 대기 열]

탈출 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2928    Accepted Submission(s): 817
Problem Description
끔찍 한 일이 생 겨 서 지금 모두 도망 치 느 라 바쁘다.하지만 도망 가 는 통 로 는 좁 아 한 줄 로 줄 을 설 수 밖 에 없 었 다.
현재 n 명 이 있 습 니 다. 1 번 부터 n 번 까지 입 니 다.동시에 일부 이상 한 제약 조건 이 있 는데 모두 a 는 b 전에 있어 야 한다.
동시에 사 회 는 불평 등하 다. 이 사람들 은 가난 한 사람 도 있 고 부자 도 있다.1 번 이 가장 부유 하고 2 번 이 두 번 째 로 부유 하 다 는 것 으로 유추 된다.부 자 는 책임자 에 게 뇌물 을 주기 때문에 그들 은 약간의 이익 이 있다.
담당 자 는 이제 모두 가 줄 을 서 는 순 서 를 정할 수 있 는데, 혜택 을 받 았 기 때문에 1 번 을 최대한 앞 세 워 야 하고, 이때 여러 가지 상황 이 있 으 면 2 번 을 최대한 앞 세 워 야 하고, 여러 가지 상황 이 있 으 면 3 번 을 최대한 앞 세 워 야 한 다 는 식 으로 유추 된다.
그럼 순 서 를 정 해 야 지.우 리 는 반드시 해 가 있 을 것 이 라 고 보장 한다.
 
Input
첫 번 째 줄 의 정수 T (1 < = T < = 5) 는 테스트 데이터 의 개 수 를 나타 낸다.
그 다음 에 각 테스트 데이터 에 대해 첫 번 째 줄 은 두 개의 정수 n (1 < = n < = 30000) 과 m (1 < = m < = 100000) 로 각각 인원수 와 제약 의 개 수 를 나타 낸다.
그리고 m 줄, 줄 마다 두 개의 정수 a 와 b 는 제약 a 호가 b 호 이전에 있어 야 한 다 는 것 을 나타 낸다.a 와 b 는 반드시 다르다.
 
Output
모든 테스트 데이터 에 대해 줄 을 서 는 순 서 를 출력 하고 빈 칸 으로 구분 합 니 다.
 
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
   
   
   
   

 
Author
CLJ
 
Source
BestCoder Round #1
 
Recommend
We have carefully selected several similar problems for you:   5609  5608  5607  5606  5605 
 
이 문 제 는 역방향 토폴로지 정렬 에 해당 합 니 다. 작은 것 은 가능 한 한 앞 에 놓 아야 하기 때 문 입 니 다. 만약 에 정방 향 토폴로지 라면 우선 순위 가 작은 값 으로 설정 해 야 합 니 다. 그러면 만약 에 작은 요구 가 없 는 점 (0 에서 0 입) 이 나타 나 면 바로 넣 습 니 다. 그러면 뒤에 더 작은 점 이 있 으 면 오류 가 발생 합 니 다. 그래서 역방향 토폴로지 를 오른쪽 에서 왼쪽으로 생각해 야 합 니 다.모든 특수 조건 은 누가 그 뒤의 점 에 먼저 넣 어야 하 는 지 밝 히 지 않 았 다.
자유의 점 은 최대한 뒤로 가 야 하지만, 정방 향 이 라면 자유 점 이 가장 먼저 입 대 했 을 것 이 므 로 역방향 으로 가 야 한 다 는 것 이다.

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <bits/stdc++.h>
using namespace std;


vector<int>point[30000+100];
priority_queue<int> q;
int out[30000+100];
int ans[30000+100];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		
		for(int i=1 ; i<=n ; ++i)
		{
			point[i].clear();
		}
		memset(out,0,sizeof out);
		while(!q.empty())
		{
			q.pop();
		}
		
		while(m--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			point[b].push_back(a);
			out[a]++;
		}
		for(int i=1 ; i<=n ; ++i)
		{
			if(out[i]==0)
				q.push(i);
		}
		int p=n-1;
		while(!q.empty())
		{
			int t=q.top();
			ans[p--]=t;
			q.pop();
			for(int i=0 ; i<point[t].size() ; ++i)
			{
				int &a=point[t][i];
				if(--out[a]==0)//  -1   0
				{
					q.push(a);
				}
			}
		}
		for(int i=0 ; i<n ; ++i)
		{
			if(i==0)
				printf("%d",ans[i]);
			else
				printf(" %d",ans[i]);
		}
		printf("
");
	}
	return 0;
}