HDU 4857: 탈출 [토폴로지]

탈출 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2416    Accepted Submission(s): 680
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
   
   
   
   

 
인접 표를 만 들 고 ~ 우선 대기 열 을 저장 하고 ~ 출력 ~ 주의 ~ 거꾸로 ~
AC-code:

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int ind[30005],que[30005],head[100005],n;
struct node
{
	int to,next;
}A[100005];
void topo()
{
	int t=0,i,j,top;
	priority_queue<int>q;
	for(i=1;i<=n;i++)
		if(ind[i]==0)
			q.push(i);
	while(!q.empty())
	{
		int top=q.top();
		q.pop();
		que[t++]=top;
		for(i=head[top];i!=-1;i=A[i].next)
		{
			ind[A[i].to]--;
			if(ind[A[i].to]==0)
				q.push(A[i].to);
		}
	}
	printf("%d",que[n-1]);
	for(i=n-2;i>=0;i--)
		printf(" %d",que[i]);
	printf("
");
}
int main()
{
	int t,m,i,a,b;
	scanf("%d",&t);
	while(t--)
	{
		memset(head,-1,sizeof(head));
		memset(ind,0,sizeof(ind));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			A[i].to=a;
			A[i].next=head[b];
			head[b]=i;
			ind[a]++;
		}
		topo();
	}
	return 0;
}