PAT Advanced 1004. Counting Leaves
1. Problem Description:
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
2. Input Specification:
Each input file contains one test case. Each case starts with a line containing \(0<N<100\), the number of nodes in a tree, and \(M\) (\(<N\)), 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-digit ID
's of its children. For the sake of simplicity, let us fix the root ID to be 01
.
The input ends with \(N\) being 0. That case must NOT be processed.
3. 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 and 02
is its only child. Hence on the root 01
level, there is 0
leaf node; and on the next level, there is 1
leaf node. Then we should output 0 1
in a line.
4. Sample Input:
2 1
01 1 02
5. Sample Output:
0 1
6. Performance Limit:
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
思路:
题目涉及树这种数据结构,要求统计每一层叶子结点(无子结点的结点)的个数。处理方法类似于PAT Advanced 1003. Emergency 中对图的处理(因为树本身就是一种特殊的图),这里根据题意定义二维数组tree[MAX_SIZE][MAX_SIZE]
存储每个结点的子结点信息,定义子函数traverseTree()
对树进行递归遍历,变量levelNow
表示当前层数,将每一层叶子节点的个数保存在int型数组res
中,这里一开始将res
定义为了map<int, int>
类型,想着方便进行输出(不用额外考虑树的深度),但是会导致无法记录某一层叶子结点为0的情况,就改成了int数组类型并额外维护变量maxLevel
记录树的深度。另外就是考虑到两个结点有公共子结点时会导致重复计数,就维护了int型数组visitFlag
保证每个叶子结点只被记录一次(不过把这个判断条件去掉也能AC,貌似树的结构已经保证了每个结点只有一个父节点?)。
参考大佬题解:1004. Counting Leaves (30)-PAT甲级真题(bfs,dfs,树的遍历,层序遍历)_柳婼的博客-CSDN博客 ,使用了dfs算法(其实我这个就相当于dfs算法 QAQ)。
My Code & Result:
#include <iostream>
//#include <map>
#define MAX_SIZE 100
using namespace std;
void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE]);
int main(void)
{
int tree[MAX_SIZE][MAX_SIZE] = {0};
int n=0, m=0;
int tempId=0, tempCount=0, tempChild=0;
int i=0, j=0; // iterator
// map<int, int> res; // count every level's leaf node
int maxLevel=0, res[MAX_SIZE+1] = {0}; // use array to count, for map can't count zero
int visitFlag[MAX_SIZE] = {0}; // make sure all node count once
cin >> n >> m;
if(!n) return 0; // n==0, return directly
for(i=0; i<m; ++i)
{
cin >> tempId >> tempCount;
for(j=0; j<tempCount; ++j)
{
cin >> tempChild;
tree[tempId][tempChild] = 1;
}
}
traverseTree(tree, 1, 1, &maxLevel, res, visitFlag);
for(i=1; i<=maxLevel; ++i)
{
if(i==1) cout << res[i];
else cout << " " << res[i];
}
cout << endl;
// for(const auto &w: res)
// {
// cout << w.first << ": " << w.second << endl;
// }
return 0;
}
void traverseTree(int tree[MAX_SIZE][MAX_SIZE], int idNow, int levelNow, int *maxLevel, int res[MAX_SIZE], int visitFlag[MAX_SIZE])
{
int i=0; // iterator
int flag=0; // have child flag
if(levelNow > *maxLevel) *maxLevel = levelNow;
for(i=0; i<MAX_SIZE; ++i)
{
if(tree[idNow][i])
{
flag = 1;
traverseTree(tree, i, levelNow+1, maxLevel, res, visitFlag);
}
}
if(!flag && !visitFlag[idNow]) // have no child && visit first time
{
visitFlag[idNow] = 1;
++res[levelNow];
}
// if(!flag) ++res[levelNow]; // have no child
return;
}
Compiler
C++ (g++)
Memory
456 / 65536 KB
Time
4 / 400 ms
标签:结点,PAT,int,MAX,Leaves,tree,1004,ID,SIZE
From: https://www.cnblogs.com/tacticKing/p/17366315.html