这是一个结论题。。
要求的序=反图的最大字典序
也就是尽量把大的放在后面。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; struct node { int x,y,next; }a[110000];int len,last[110000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } priority_queue<int>q; int du[110000],as[110000]; int main() { int T; scanf("%d",&T); while(T--) { int n,m,x,y; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); memset(du,0,sizeof(du)); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(y,x);du[x]++; } for(int i=1;i<=n;i++) if(du[i]==0)q.push(i); bool bk=true; for(int i=1;i<=n;i++) { if(q.empty()){bk=false;break;} int x=q.top();q.pop(); as[i]=x; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; du[y]--; if(du[y]==0)q.push(y); } } if(bk==false)printf("Impossible! "); else { for(int i=n;i>1;i--)printf("%d ",as[i]); printf("%d ",as[1]); } } return 0; }