题目大意：有$m$组约束关系$(x_i,y_i)$，你要构造一个排列，满足数$x_i$出现在数$y_i$前面，请使得这个排列字典序最小，请输出这个排列。无解请输出-1。
数据范围：$n,m≤10^5$
我们把约束关系$(x_i,y_i)$视作从$y_i$连向$x_i$的有向边，于是我们得到了一个有向图，无解情况下该图会存在环。
我们对这个有向图进行拓扑排序即可，只不过每次出队的点是当前队列中编号最大的点。
我们开一个数组$ans$，记$ans_i$表示第i次出队的点的编号。
若原图中存在环，显然$|ans|≠n$，我们可以通过该性质判断是否有解。
否则倒着输出$ans$数组即可。
关于正确性可以这么理解：当第$x$个点出队时，所有依赖于该点的点都出队了，且当前编号大于它的点都出队了。
1 #include<bits/stdc++.h> 2 #define M 100005 3 using namespace std; 4 5 vector<int> v[M]; 6 int n,m,vis[M]={0}; 7 int ans[M]={0},in[M]={0},cnt=0; 8 priority_queue<int> q; 9 int Main(){ 10 memset(in,0,sizeof(in)); 11 memset(ans,0,sizeof(ans)); cnt=0; 12 for(int i=0;i<M;i++) v[i].clear(); 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=m;i++){ 15 int x,y; scanf("%d%d",&x,&y); 16 v[y].push_back(x); in[x]++; 17 } 18 for(int i=1;i<=n;i++) if(in[i]==0) q.push(i); 19 while(!q.empty()){ 20 int u=q.top(); q.pop(); 21 ans[++cnt]=u; 22 int siz=v[u].size(); 23 for(int i=0;i<siz;i++){ 24 int V=v[u][i]; 25 in[V]--; 26 if(in[V]==0) q.push(V); 27 } 28 } 29 if(n!=cnt){ 30 printf("Impossible! "); 31 return 0; 32 } 33 for(int i=n;i;i--) printf("%d ",ans[i]); 34 } 35 int main(){ 36 int t; cin>>t; 37 while(t--) Main(); 38 }