这题不是求最小字典序。。。撕烤了半个小时才发现不对劲T T
这题是能让小的尽量前就尽量前，无论字典序...比如1能在2前面就一定要在2前面...
显然是要先拓扑排序，让小的尽量前转化成让大的尽量往后丢，这样实际上就跟字典序无关了。于是建反向图，用堆维护一下入度为0的最大值来弹出就好了。
以后拓扑排序别用for弹栈了T T WA了好久
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<queue> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int too,pre;}e[maxn]; priority_queue<int>q; int n,m,x,y,z,tot,cnt,T; int last[maxn],ru[maxn],ans[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;} void topsort() { for(int i=1;i<=n;i++)if(!ru[i])q.push(i); if(q.empty())return; while(!q.empty()) { int now=q.top();q.pop();ans[++cnt]=now; for(int i=last[now];i;i=e[i].pre) { ru[e[i].too]--; if(!ru[e[i].too])q.push(e[i].too); } } } void clear() { tot=cnt=0; while(!q.empty())q.pop(); memset(ru,0,(n+1)<<2); memset(last,0,(n+1)<<2); } int main() { read(T); while(T--) { read(n);read(m);clear(); for(int i=1;i<=m;i++)read(x),read(y),add(y,x),ru[x]++; topsort(); if(cnt<n){puts("Impossible!");continue;} for(int i=n;i;i--)printf("%d ",ans[i],i==1?' ':' ');puts(""); } return 0; }