题意：有n个数排成一列，给定m个限制(x,y),表示x应在y的前面，规定对于x1,x2，x1<x2，每个x1如果不存在一条限制路径(每个限制连一条（x,y）x=>y的边)，则x1应排在x2前面，求最终排列
算法：拓扑排序
我们如果单纯的找一个字典序最小的限制队列，这很显然是一个拓扑板子
但是这很显然没有那么简单，你仔细思考会发现，正着搞有很多的后效性，非常难搞
所以，正难则反，我们应该想可不可以反着建图
我们发现，对于最后一位，肯定是没有限制的最大的那个数，然后把对于这个数有限制的数度数减1，以此类推，我们会发现这样非常正确，并没有后效性的影响。
CODE：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define MAXN 100050
using namespace std;
struct zlk{
int x;
bool operator <(zlk a) const{
return x<a.x;
}
};
priority_queue<zlk> Q;
int de[MAXN],n,fir[MAXN],nxt[MAXN],to[MAXN],m,t,tot,q[MAXN],cnt;
void ade(int x,int y){
to[++tot]=y;
nxt[tot]=fir[x];
fir[x]=tot;
}
int main(){
cin>>t;
while(t--){
tot=0;
memset(fir,0,sizeof(fir));
memset(de,0,sizeof(de));
scanf("%d%d",&n,&m);
rep(i,1,m){
int x,y; scanf("%d%d",&x,&y);
ade(y,x); de[x]++;
}
rep(i,1,n) if(!de[i]) Q.push((zlk){i});
cnt=0;
while(!Q.empty()){
int x=Q.top().x; Q.pop();
q[++cnt]=x;
for(int k=fir[x];k;k=nxt[k]){
de[to[k]]--;
if(!de[to[k]]) Q.push((zlk){to[k]});
}
}
if(cnt!=n){puts("Impossible!"); continue;}
while(cnt) cout<<q[cnt--]<<" ";
cout<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/handsome-zlk/p/12038970.html