POJ 2367 Genealogical tree(拓扑排序:输出方案)
http://poj.org/problem?id=2367
题意:大意就是给你一个N个点的图,并且给你图中的有向边,要你输出一个可行的点拓扑序列即可.输入格式为,第一行点数N,以下接着有N行,每行以0结尾.第i行包含了以i点为起点的有向边所指的所有节点.
分析:直接用 vector G[maxn][maxn] 和in[maxn] 数组来建图和表示入度即可.
然后用队列的方式消除图的所有边,求拓扑序列即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100+10;
int n;
vector<int> G[maxn];
int in[maxn];
int ans[maxn];
void topo()
{
queue<int> Q;
for(int i=1;i<=n;i++)if(in[i]==0)
Q.push(i);
int cnt=0;
while(!Q.empty())
{
int u=Q.front(); Q.pop();
ans[cnt++]=u;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(--in[v]==0) Q.push(v);
}
}
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++)
{
G[i].clear();//初始化
in[i]=0; //初始化
int v;
while(1)
{
scanf("%d",&v);
if(v==0) break;
G[i].push_back(v);
in[v]++;
}
}
topo();
printf("%d",ans[0]);
for(int i=1;i<n;i++)
printf(" %d",ans[i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
北大POJ初级题-数据结构:解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603488
北大POJ2255-Tree Recovery 解题报告+AC代码
poj 2201 Cartesian Tree.md
NULL 博文链接:https://128kj.iteye.com/blog/1750462
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
poj 1091 拓扑排序加上foyld_warshall算法实现
NULL 博文链接:https://128kj.iteye.com/blog/1754177
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
北大POJ3414-Pots 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj与leetcode 在线裁判 这个存储库存储了我在一些在线判断中解决这些问题而编写的所有代码,例如,和。 在 Java 中 77 / 1235 问题在Leetcode中得到解决 华为解决了一小部分问题 POJ解决了一小部分问题 其他语言 去...
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1754756
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码