hdu 4857 탈출 (토폴로지 정렬 + 최소 앞 에 보장)

탈출 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 74    Accepted Submission(s): 13
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
 
생각:
이 문 제 는 사전 순 서 를 보장 하 는 것 이 아니 라 최소 로 앞 에 있어 야 합 니 다.
역방향 으로 그림 을 만 들 고 큰 우선 순 위 를 앞 에 놓 고 역순 으로 출력 합 니 다.
우선 거꾸로 그림 + 역순 으로 출력 하 는 것 이 답 입 니 다.그리고 가장 작은 것 이 맨 앞 에 있 도록 해 야 합 니 다. 역순 출력 이기 때문에 우선 순 위 는 반대로 해 야 합 니 다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define maxn 30005
using namespace std;

int n,m,ans;
bool vis[maxn];
int in[maxn];
vector<int>edge[maxn];

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(in,0,sizeof(in));
        for(i=1;i<=n;i++) edge[i].clear();
        int u,v;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            in[u]++;
            edge[v].push_back(u);
        }
        priority_queue<int> q;
        for(i=1;i<=n;i++)
        {
            if(in[i]==0) q.push(i);
        }
        memset(vis,0,sizeof(vis));
        vector<int>res;
        ans=0;
        while(!q.empty())
        {
            ans++;
            u=q.top();
            res.push_back(u);
            q.pop();
            vis[u]=1;
            for(i=0;i<edge[u].size();i++)
            {
                v=edge[u][i];
                in[v]--;
                if(in[v]==0) q.push(v);
            }
        }
        for(i=res.size()-1;i>=0;i--)
        {
            if(i==res.size()-1) printf("%d",res[i]);
            else printf(" %d",res[i]);
        }
        puts("");
    }
    return 0;
}
/*
20
4 3
4 1
4 2
3 2
*/