题意：给定限制条件(a,b)表示a必须在b之前，求所有合法序列中，小的数尽量在前面的方案
题解：首先我们根据限制条件建反向图，然后在反向图上求字典序最小的拓扑序（队列改为堆），逆序输出即可。
#include#include #include #include #include #include #include using namespace std;const int MAXN=100000+2;struct HASH{ int u; HASH *next; HASH(){} HASH(int _u,HASH *_next):u(_u),next(_next){}}*table[MAXN],mem[MAXN*2];int N,M,Q,cnt,ans[MAXN],degree[MAXN];priority_queue q;void Insert(int u,int v){ table[u]=&(mem[cnt++]=HASH(v,table[u]));}void Topology_Sort(){ while(!q.empty()) q.pop(); for(int i=1;i<=N;i++) if(!degree[i]) q.push(i); while(!q.empty()){ ans[++cnt]=q.top(),q.pop(); for(HASH *p=table[ans[cnt]];p;p=p->next){ degree[p->u]--; if(!degree[p->u]) q.push(p->u); } }}int main(){ scanf("%d",&Q); while(Q--){ memset(table,0,sizeof(table)); memset(degree,0,sizeof(degree)); cnt=0; scanf("%d %d",&N,&M); for(int i=1,u,v;i<=M;i++){ scanf("%d %d",&u,&v); Insert(v,u),degree[u]++; } cnt=0,Topology_Sort(); if(cnt!=N) printf("Impossible!\n"); else{ for(int i=N;i;i--) printf("%d ",ans[i]); printf("\n"); } } return 0;}