PAT Advanced 1004. Counting Leaves()-其他

发表于： 5月 1, 2023 5月 1, 2023
分类：其他
标签：其他

PAT Advanced 1004. Counting Leaves()

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 is a two-digit number representing a given non-leaf node, is the number of its children, followed by a sequence of two-digit ‘s of its children. For the sake of simplicity, let us fix the root ID to be .

ID

ID

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 is the root and is its only child. Hence on the root level, there is leaf node; and on the next level, there is leaf node. Then we should output in a line.

0 1

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 中对图的处理（因为树本身就是一种特殊的图），这里根据题意定义二维数组存储每个结点的子结点信息，定义子函数对树进行递归遍历，变量表示当前层数，将每一层叶子节点的个数保存在int型数组中，这里一开始将定义为了类型，想着方便进行输出（不用额外考虑树的深度），但是会导致无法记录某一层叶子结点为0的情况，就改成了int数组类型并额外维护变量记录树的深度。另外就是考虑到两个结点有公共子结点时会导致重复计数，就维护了int型数组保证每个叶子结点只被记录一次（不过把这个判断条件去掉也能AC，貌似树的结构已经保证了每个结点只有一个父节点？）。

tree[MAX_SIZE][MAX_SIZE]

traverseTree()

levelNow

res

res

map<int, int>

maxLevel

visitFlag

参考大佬题解：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

————————