首页 > 代码库 > BZOJ 4010 拓扑排序+heap

BZOJ 4010 拓扑排序+heap

思路:

反向图求最大拓扑序 反向输出

//By SiriusRen#include <queue>#include <cstdio>#include <cstring>using namespace std;const int N=200050;int cases,n,m,xx,yy,du[N],first[N],next[N],v[N],w[N],tot,ans[N],top;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}priority_queue<int>pq;int main(){    scanf("%d",&cases);    while(cases--){        memset(first,-1,sizeof(first)),tot=top=0;        memset(du,0,sizeof(du));        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++){            scanf("%d%d",&xx,&yy);            add(yy,xx),du[xx]++;        }        for(int i=1;i<=n;i++)if(!du[i])pq.push(i);        while(!pq.empty()){            int t=pq.top();pq.pop();            ans[++top]=t;            for(int i=first[t];~i;i=next[i]){                du[v[i]]--;                if(!du[v[i]])pq.push(v[i]);            }        }        if(top!=n){puts("Impossible!");continue;}        for(int i=top;i;i--)printf("%d ",ans[i]);puts("");    }}

 

BZOJ 4010 拓扑排序+heap