一开始，没想出来，先topsort判环，把impossible拿到手，然后划分联通块，对每个联通块跑一遍topsort，觉得可对了，然后被大样例教育明白了，知道自己的策略错在哪了。
接着在纸上疯狂手模样例，不停地换topsort的顺序和贪心的方法，然后发现一种可行的解法。
开大根堆，对反图跑topsort，然后倒序输出。
这是一种贪心的策略，通过上述操作，我们可以使不但大，而且限制多的不优秀点在最后输出，而小而且限制少的在前输出，既不违反规则，字典序又最小。
换另一种解释，题目要我们输出满足拓扑序的最小字典序，是两个可能矛盾的量，他们之间可能存在冲突，那我们就倒着来，找满足拓扑逆序的最大字典序，这两个量都可以否定一个数字出现在靠前位置，把它们先找出来，然后倒着输出，就可以了。
其实上述过程只用一个topsort就搞定了，但是博主略懒，以前的那个top判环没删，就直接用了，导致时间略长。大家还是自己去打打吧，就当复习topsort了。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> #include<stack> using namespace std; int read(){ int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){ if(x=='-') f=-1; x=getchar(); }while(x>='0'&&x<='9'){ sum=sum*10+x-'0'; x=getchar(); }return sum*f; } int T,n,m,du[100500],pos[100500],ans[100500],size[100500],du1[100500],cnt; vector<int>edge[100500]; vector<int>lcc[100500]; vector<int>e[100500]; bool v[100500]; map<pair<int,int>,bool>mp[5]; bool check(){ bool vis[100500]; memset(vis,0,sizeof(vis)); queue<int>tops; while(!tops.empty()) tops.pop(); for(int i=1;i<=n;i++) if(du[i]==0){ tops.push(i); vis[i]=1; // cout<<i<<" "; } while(!tops.empty()){ int x=tops.front(); tops.pop(); for(int i=0;i<edge[x].size();i++){ int y=edge[x][i]; du[y]--; if(du[y]==0){ tops.push(y); vis[y]=1; // cout<<y<<" "; } } }//cout<<endl; /* for(int i=1;i<=n;i++) cout<<vis[i]<<" ";*/ for(int i=1;i<=n;i++) if(!vis[i]) return 1; return 0; } void topsort(){ priority_queue<int>q; for(int i=1;i<=n;i++) if(du1[i]==0) q.push(i); while(!q.empty()){ int x=q.top();q.pop();ans[++ans[0]]=x; for(int i=0;i<e[x].size();i++){ int y=e[x][i]; du1[y]--; if(du1[y]==0) q.push(y); } } } int main(){ /*freopen("1.in","r",stdin); freopen("1.out","w",stdout);*/ T=read(); while(T--){ n=read();m=read(); memset(ans,0,sizeof(ans)); memset(du,0,sizeof(du)); memset(v,0,sizeof(v)); memset(du1,0,sizeof(du1)); memset(e,0,sizeof(e)); for(int i=1;i<=n;i++) edge[i].clear(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); if(mp[T][make_pair(x,y)]) continue; mp[T][make_pair(x,y)]=1; edge[x].push_back(y); // e[x].push_back(y); e[y].push_back(x); du[y]++; du1[x]++; } if(check()){ puts("Impossible!"); continue; } topsort(); for(int i=n;i>=1;i--) printf("%d ",ans[i]); putchar(' '); } return 0; }