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