PAT 1004 Counting Leaves
程序员文章站
2022-06-11 15:03:03
...
PAT 甲级 1004 Counting Leaves
题目要求:
中文:
家系的层次结构通常由系谱树表示。你的工作是统计那些没有孩子的家庭成员。
输入规格:
每个输入文件包含一个测试用例。每种情况都以一行开始,其中包含0然后是M行,每一行的格式如下:
ID K ID[1] ID[2]…ID [K]
- 其中ID是一个两位数的数字,表示给定的非叶节点,K是它的子节点的数目,然后是它的子节点的两位数ID的序列。为了简单起见,我们将根ID修改为01。
- 输入以N = 0结束。那件案子必须不予处理。
输出规范:
- 对于每个测试用例,您应该将那些没有孩子的家庭成员从根开始算起。数字必须打印成一行,中间用空格隔开,每行的末尾不能有多余的空格。
- 示例用例表示一个只有2个节点的树,其中01是根节点,02是惟一的子节点。因此,在根01层,有0个叶节点;下一层,有一个叶节点。然后我们应该在一行中输出0 1。
题目大意:
其实就是找一棵树每一层的孩子节点的个数,第一行的两个数字,N和M代表,一共有N个节点,M个叶子节点
从第二行开始,每一行第一个数字代表当前非叶子节点的索引值,直接用int存就可以,因为int类型会自动把前面的0消除;第二个数字代表当前节点有几个孩子(不一定是二叉树哈),后面跟着一串孩子节点的索引值,以此类推。
解题思路:
- 首先要考虑如何存储的问题,为了简便算法,采用静态链式存储结构—“孩子节点”表示方法,结构体由一个索引值,孩子个数值和一个vector组成,vector用来存储一系列孩子的索引。
- 其实本题可以采用多种遍历方法,除了层次便利以外,还可以使用DFS去递归寻找不同层次的子节点。
- 本文采用层次遍历的方法,设立height记录当前层数,设立last指针始终指向下一层的最后一个节点,使用last_point指针指向当前层的最后一个节点。用leaf_num数组,记录每一层的叶子节点的个数。
代码:
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
typedef struct Node{
int vec;
int child_num;
vector<int> childs;
}Tree;
int main(){
int N,M;
bool visited[110]; //设立访问数组
Tree *tree = new Tree[110];//使用静态结构存储树
int leaf_num[110]; //用来记录每层的叶子节点个数
fill(leaf_num,leaf_num+110,0); //初始化leaf_num的值
scanf("%d%d",&N,&M);
if(N == 0){
printf("0");
return 0;
}
int i,j;
for(i=1;i<=N;i++){ //对树的存储结构进行初始化操作
tree[i].vec = i;
tree[i].child_num = 0;
}
for(i=1;i<=M;i++){ //初始化每一个非叶子节点
int current_id,kids,kids_num;
scanf("%d%d",¤t_id,&kids_num);
tree[current_id].child_num = kids_num;
for(j=0;j<kids_num;j++){
scanf("%d",&kids);
tree[current_id].childs.push_back(kids);
}
}
//利用BFS对树进行遍历
queue<int> que; //初始化队列
que.push(1);
int last_point = 1,last=1; //记录当前层的最后一个节点的编号
int height = 0; //记录当前的层数
int v;
while(!que.empty()){
v = que.front();
que.pop();
visited[v] = true; //该节点已经访问过
if(tree[v].child_num == 0){
leaf_num[height]++;
}else{
for(i=0;i<tree[v].child_num;i++){
if(!visited[tree[v].childs[i]]){
que.push(tree[v].childs[i]);
last = tree[v].childs[i];
}
}
}
if(v == last_point){
height ++;
last_point = last;
}
}
//最后输出每一层的叶子节点的个数
for(i=0;i<height;i++){
if(i < height-1){
printf("%d ",leaf_num[i]);
}else{
printf("%d",leaf_num[i]);
}
}
return 0;
}