P3243 菜肴制作

这道题难点就在如何贪心，这里要我们让最小的尽可能优先做而不是字典序最小，那我们让大的尽可能后做，是不是就可以把最小的尽可能优先做呢？而这样相当于是反过来的序列字典序最大，所以我们跑个反图最大字典序拓扑即可，即建反图以后用优先队列维护最大点。

\(Code\)

const int N=1e5+5;
int inn[N],ans[N],tot;
vector<int>f[N];
priority_queue<int>Q;
int main(){
    for(int T=read();T--;tot=0){
        int n=read(),m=read();
        for(int i=1;i<=n;i++)f[i].clear(),inn[i]=0;
        for(int i=1;i<=m;i++){
            int u=read(),v=read();
            f[v].push_back(u),inn[u]++;
        }
        for(int i=1;i<=n;i++)if(!inn[i])Q.push(i);
        while(!Q.empty()){
            int x=Q.top();Q.pop();
            ans[++tot]=x;
            for(int y:f[x])
                if(!--inn[y])Q.push(y);
        }
        if(tot==n)for(int i=n;i;--i)printf("%d ",ans[i]);
        else printf("Impossible!");
        puts("");
    }
    return 0;
}