首页 > 代码库 > 图论之拓扑排序 poj 2367 Genealogical tree
图论之拓扑排序 poj 2367 Genealogical tree
题目链接 http://poj.org/problem?id=2367
题意就是给定一系列关系,按这些关系拓扑排序。
#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxn=200; int ans; int n; int in[maxn]; //记录入度 int num[maxn]; //记录答案 vector<int>E[maxn]; //记录边 void topo_sort() //拓扑排序 { queue<int>q; for(int i=1; i<=n; i++) if(!in[i]) { q.push(i); in[i]=-1; } while(!q.empty()) { int now=q.front(); num[ans]=now; ans++; q.pop(); for(int i=0; i<E[now].size(); i++) if(in[E[now][i]]>0) in[E[now][i]]--; for(int i=1; i<=n; i++) if(!in[i]) { in[i]=-1; q.push(i); } } return ; } int main() { while(~scanf("%d",&n)) { memset(num,0,sizeof(num)); memset(in,0,sizeof(in)); for(int i=0;i<maxn;i++) E[i].clear(); ans=0; for(int i=1; i<=n; i++) { int x; while(scanf("%d",&x)) { if(!x) break; E[i].push_back(x); in[x]++; } sort(E[i].begin(),E[i].end()); } topo_sort(); printf("%d",num[0]); for(int i=1; i<n; i++) printf(" %d",num[i]); puts(""); } return 0; }
图论之拓扑排序 poj 2367 Genealogical tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。