hdu-4857-逃生-拓扑排序

本文主要是介绍hdu-4857-逃生-拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

拓扑排序。

反向建边。

为了序号小的尽量在前面，我们每次都取出入度为0的最大的点。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
struct list
{int u,v,w;int next;
}edge[110000];
int head[33000];
int nums;
void add(int u,int v,int w)
{edge[nums].u=u;edge[nums].v=v;edge[nums].w=w;edge[nums].next=head[u];head[u]=nums++;
}
int du[33000];
void init()
{memset(head,-1,sizeof(head));nums=1;memset(du,0,sizeof(du));
}
priority_queue<int>que;
vector<int>vec;
int n;
void dos()
{vec.clear();while(!que.empty())que.pop();for(int i=1;i<=n;i++){if(du[i]==0)que.push(i);}while(!que.empty()){int x=que.top();que.pop();for(int i=head[x];i!=-1;i=edge[i].next){int y=edge[i].v;du[y]--;if(du[y]==0){que.push(y);}}vec.push_back(x);}for(int i=n-1;i>=0;i--){if(i!=n-1)printf(" ");printf("%d",vec[i]);}cout<<endl;
}
int main()
{int T,m,a,b;scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);add(b,a,1);du[a]++;}dos();}return 0;
}

这篇关于hdu-4857-逃生-拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---