首页 > 代码库 > hdu-4857 逃生 拓扑排序
hdu-4857 逃生 拓扑排序
http://acm.hdu.edu.cn/showproblem.php?pid=4857
思路--优先队列+反向拓扑+逆序输出
把受限制条件多的先弹出到数组里,然后再弹出不受限制的(用优先队列按序号从大到小),最后逆序输出。
#include<cstdio> #include<queue> #include<vector> #include<cstring> using namespace std; #define N 30001 int n,in[N],num[N],cnt; vector<int>v[N]; priority_queue<int,vector<int>,less<int> >q; //大根堆 void init() { cnt=0; for(int i=0;i<=n;i++) v[i].clear(); memset(in,0,sizeof(in)); memset(num,0,sizeof(num)); while(!q.empty()) q.pop(); } void top_sort() { for(int i=1;i<=n;i++) if(in[i]==0) q.push(i); while(!q.empty()) { int w=q.top(); q.pop(); num[cnt++]=w; for(int i=0;i<v[w].size();i++) { in[v[w][i]]--; if(in[v[w][i]]==0) q.push(v[w][i]); } } } int main() { //freopen("a.txt","r",stdin); int t,m,x,y; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&x,&y); v[y].push_back(x); in[x]++; } top_sort(); printf("%d",num[cnt-1]); //逆序输出 for(int i=cnt-2;i>=0;i--) printf(" %d",num[i]); printf("\n"); } return 0; }
hdu-4857 逃生 拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。