欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT 1004 Counting Leaves

程序员文章站 2022-06-11 15:03:03
...

PAT 甲级 1004 Counting Leaves

题目要求:

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",&current_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;
}