洛谷P3243 [HNOI]菜肴制作——拓扑排序

题目：/problemnew/show/P3243

正向按字典序拓扑排序很容易发现是不对的，因为并不是序号小的一定先做；

但若让序号大的尽可能放在后面，则不会有什么问题，因为它不影响它前面的选择；

我们可以建反图，从后往前按序号从大到小排序，倒序输出答案，这样就把序号大的尽量放在后面了。

代码如下：

#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;priority_queue<int>q;int const maxn=1e5+5;int D,n,m,rd[maxn],head[maxn],ct,ans[maxn],cnt;struct N{int to,next;N(int t=0,int n=0):to(t),next(n) {}}edge[maxn];void topo(){for(int i=1;i<=n;i++)if(!rd[i])q.push(i);cnt=0;while(q.size()){int x=q.top();q.pop();ans[++cnt]=x;for(int i=head[x];i;i=edge[i].next){int v=edge[i].to;rd[v]--;if(!rd[v])q.push(v);}}if(cnt<n)printf("Impossible!\n");else{for(int i=cnt;i;i--)printf("%d ",ans[i]);printf("\n");}}int main(){scanf("%d",&D);while(D--){memset(rd,0,sizeof rd);memset(head,0,sizeof head);ct=0;scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);edge[++ct]=N(x,head[y]);head[y]=ct;rd[x]++;}topo();}return 0;}