本题坑点

题目没有给数据规模，我去别的oj网站上查了，是 100%的数据满足N,M<=100000,D<=3

解题思路

“看到x要先于y”这类字的时候，第一反应就是拓扑排序（不知道拓扑排序点这里 ），但是有一个问题，如果用拓扑排序，我们只能得到字典序最小的方案， 不能满足题目要求的使得小A能尽量先吃到质量高的菜肴，那怎么解决这个问题呢？我们在做拓扑排序的过程中，会优先考虑路线的起点编号大小，但是我们的目标却是使得每次选取的路线终点的编号最小，那么我们可以通过反向建边，寻找字典序最大的方案，最后反序输出就可以了

注意事项

重边问题

本题存在重边，所以不能在加边的时候就统计入度，去除重边的方法很多，我这里用的是stl里面的set

多组数据

记得每次清空各种数组和变量，防止影响下一组数据

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector> 
#include<set>
using namespace std;
const int mx=101010;
int n,m;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
struct Heap{
    int size;
    int h[mx];
    void push(int x){
        h[++size]=x;
        int now=size;
        int fa=now>>1;
        while(fa>=1){
            if(cmp(h[now],h[fa])){
                swap(h[fa],h[now]);
                now=fa;
                fa=now>>1;
            }
            else break;        
        }
    }
    void pop(){
        swap(h[1],h[size]);
        size--;
        int now=1;
        int son=now<<1;
        while(son<=size){
            if((son|1)<=size&&cmp(h[son|1],h[son]))son|=1;
            if(cmp(h[son],h[now])){
                swap(h[son],h[now]);
                now=son;
                son=now<<1;
            }
            else break;
        }
    }
    bool cmp(const int a,const int b){//用于控制小根堆还是大根堆 
        return a>b;
    }
    int top(){
        return h[1];
    }
    bool empty(){
        return size==0;
    }
}heap;
set<int>go[mx];
int ans[mx];
int num;
int ind[mx];//每个点入度 
int main(){
    int T=Read();
    while(T--){
        num=0;
        n=Read(),m=Read();
        for(int i=1;i<=m;++i){
            int u=Read(),v=Read();
            go[v].insert(u);
        }
        for(int i=1;i<=n;++i){
            for(set<int>::iterator it=go[i].begin();it!=go[i].end();++it){
                ind[*it]++;
            }
        }
        for(int i=1;i<=n;++i){
            if(!ind[i]){
                heap.push(i);    
            }
        }
        while(!heap.empty()){
            int u=heap.top();
            heap.pop();
            ans[++num]=u;
            if(go[u].empty())continue;
            set<int>::iterator it=go[u].end();
            do{
                --it;
                int v=*it;
                ind[v]--;
                if(!ind[v])heap.push(v);
            }while(it!=go[u].begin());
        }
        if(num!=n){
            printf("Impossible!\n");
        }
        else{
            for(int i=n;i>=1;--i){
                printf("%d ",ans[i]);
            }
            printf("\n");
        }
        //清空数据 
        memset(ind,0,sizeof(ind));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;++i)go[i].clear();//清空边 
    }

    return 0;
}