PAT_A1004#Counting Leaves
Source:
Description:
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0, the number of nodes in a tree, and M (<), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where
ID
is a two-digit number representing a given non-leaf node,K
is the number of its children, followed by a sequence of two-digitID
's of its children. For the sake of simplicity, let us fix the root ID to be01
.The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where
01
is the root and02
is its only child. Hence on the root01
level, there is0
leaf node; and on the next level, there is1
leaf node. Then we should output0 1
in a line.
Sample Input:
2 1
01 1 02
Sample Output:
0 1
Keys:
Code:
/*
time: 2019-06-28 16:47:33
problem: PAT_A1004#Counting Leaves
AC: 16:22 题目大意:
统计各层的叶子结点个数
输入:
第一行给出,结点数N<100,分支结点数M
接下来M行,结点id,孩子数k,孩子id(1~n,root==1)
多组输入样例 基本思路:
遍历并记录各层叶子结点数即可
*/
#include<cstdio>
#include<vector>
using namespace std;
const int M=;
vector<int> tree[M];
int leaf[M],level=; void Travel(int root, int hight)
{
if(tree[root].size()==)
{
if(hight > level)
level = hight;
leaf[hight]++;
return;
}
for(int i=; i<tree[root].size(); i++)
Travel(tree[root][i],hight+);
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE int n,m;
while(~scanf("%d", &n))
{
level=;
for(int i=; i<=n; i++){
tree[i].clear();
leaf[i]=;
}
scanf("%d", &m);
for(int i=; i<m; i++)
{
int id,k,kid;
scanf("%d%d", &id,&k);
for(int j=; j<k; j++)
{
scanf("%d", &kid);
tree[id].push_back(kid);
}
}
Travel(,);
for(int i=; i<=level; i++)
printf("%d%c", leaf[i], i==level?'\n':' '); } return ;
}
最新文章
- linux下libuv库安装教程
- ThinkPHP 3.2.3(三)架构之URL模式
- 安装好oracle后,打开防火墙遇到的问题!
- Spring(七)持久层
- SPRING IN ACTION 第4版笔记-第十一章Persisting data with object-relational mapping-005Spring-Data-JPA例子的代码
- 关闭“编辑窗体”后, 主窗体的DatagridView刷新数据的问题
- cocos2d-x游戏开发实战原创视频讲座系列1之2048游戏开发
- Learn Objectvie-C on the Mac 2nd Edition 笔记
- mysql 新增 删除用户和权限分配
- 9.XML文件解析
- JavaWeb之Listener监听器
- document.querySelectorAll() 与document.getElementTagName() 的区别
- c#之文件操作(学习笔记)
- 【Unity技巧】自定义消息框(弹出框)
- maven war项目完整配置
- Linux进程被杀掉(OOM killer),查看系统日志
- html页面字体相关
- 一点不懂到小白的linux系统运维经历分享
- eclipse安装properties插件
- 基于Centos搭建 Firekylin 个人网站