hdu4857(拓扑排序，反向遍历)

逃生
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7914    Accepted Submission(s): 2308

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代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define LL long long
const int MOD=998244353;
const int inf=0x3f3f3f3f;
const LL MAX_N=30005;
const LL MAX_M=100005;
#define MEF(x) memset(x,-1,sizeof(x))
#define ME0(x) memset(x,0,sizeof(x))
#define MEI(x) memset(x,inf,sizeof(x))
struct LX
{
    int v,next;
}lx[MAX_M];
int rd[MAX_N];
int first[MAX_N],vis[MAX_N];
int cnt;
priority_queue<int> q;
void add(int u,int v)
{
    rd[u]++;
    lx[++cnt].v=u;
    lx[cnt].next=first[v];
    first[v]=cnt;
}
void solve(int n)
{
    int nt=0,ans[MAX_N];
    for(int n1=1;n1<=n;n1++)
    {
        if(rd[n1]==0)
        {
            q.push(n1);
            vis[n1]=1;
        }
    }
    while(!q.empty())
    {
        int x=q.top();
        ans[++nt]=x;
        q.pop();
        for(int i=first[x];i!=-1;i=lx[i].next)
        {
            int y=lx[i].v;
            rd[y]--;
            if(!vis[y]&&rd[y]==0)
            {
                q.push(y);
                vis[y]=1;
            }
        }
    }
    for(int nt1=nt;nt1>=1;nt1--)
    {
        if(nt1==nt)
        {
            printf("%d",ans[nt1]);
        }
        else
        {
            printf(" %d",ans[nt1]);
        }
    }
    printf("\n");
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int t1=1;t1<=t;t1++)
    {
        int n,m,v,u;
        scanf("%d%d",&n,&m);
        cnt=0;
        MEF(first);
        ME0(rd);
        ME0(vis);
        for(int m1=1;m1<=m;m1++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        solve(n);
    }
    return 0;
}