首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。