题目质量非常好  题意很简单，用的知识点也很简单   拓扑排序+ 优先队列

也可以在杭电上提交

bestcoder round1 逃生

 

一个朴素的想法： 正常建图 ， 先把入度为0的点加入优先队列，小的在前，直接拓扑排序

BUT    WA 

WA的毫无情谊

为什么呢？  　　参考这位大佬的博客  http://blog.csdn.net/Lawliet1993/article/details/51043070

来个例子 

存在拓扑关系： 

5 -> 3 -> 1 

6 -> 4 -> 2 

直接拓扑排序的结果是 5 3 1 6 4 2，结果是正确的（1号尽可能的在前面了） ，看起来好像直接拓扑排序就可以了，但是为什么提交后却wa了呢，别急，我们再看一个例子： 

6 -> 3 -> 1 

5 -> 4 -> 2 

直接拓扑排序的结果是：5 4 2 6 3 1 ，结果是错误的，因为我们可以把1号安排到更前面的位置 即：6 3 1 5 4 2（正确答案）。 

 

大佬的思路： 正向的处理不方便，反向建图！  反向建图对拓扑序有什么影响呢？

　　正向建图的最后一个点在反向建图中会在第一个！也就是说 拓扑序会相反！  得到的拓扑序反向就是答案

根据题目要求   序号大的点应该尽量排在后面  使用优先队列，大的点排在前面 ，拓扑排序

大佬代码

#include 
      
       using namespace std;const int maxn = 31000;pair
       
         a[maxn * 4];int h[maxn];int in[maxn];int ans[maxn],cnt;int main(){    int tt;    scanf("%d",&tt);    int x,y;    while(tt--)    {        int n,m;        memset(h,0,sizeof(h));        memset(in,0,sizeof(in));        scanf("%d%d",&n,&m);        cnt = 0;        for(int i=1;i<=m;i++)        {            scanf("%d%d",&y,&x);            if(h[x] == 0){                h[x] = i;                a[i].first = y;                a[i].second = 0;                in[y]++;            }else{                int t = h[x];                h[x] = i;                a[i].first = y;                a[i].second = t;                in[y]++;            }        }        priority_queue
        
         
          , less
          
            > que;        for(int i=1;i<=n;i++)            if(in[i] == 0) que.push(i);        while( !que.empty()){            int top = que.top();            que.pop();            ans[cnt++] = top;            for(int i = h[top];i!=0;i = a[i].second){                in[a[i].first]--;                if(in[a[i].first] == 0)                    que.push(a[i].first);            }        }        for(int i=cnt -1 ;i > 0;i--)            printf("%d ",ans[i]);        printf("%d\n",ans[0]);    }}