首页 > 其他分享 >PAT Advanced 1004. Counting Leaves

PAT Advanced 1004. Counting Leaves

时间:2023-05-01 12:11:05浏览次数:60  
标签:结点 PAT int MAX Leaves tree 1004 ID SIZE

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

相关文章

  • cpp: Simple Factory Pattern
     //Monster.h:此文件包含"Monster"类。AbstractFactoryPatternC++14//2023年4月29日涂聚文GeovinDuVisualStudio2022edit.#pragmaonce#ifndefMONSTER_H#defineMONSTER_H#include<iostream>usingnamespacestd;namespaceDuAbstr......
  • vue3 vueRouter4 :No match found for location with path ***
    0.采用vue+router4做路由导航.首次载入控制台很干净.F5刷新后,控制台爆出警告,但点击路由正常工作.1.经过排查发现,是menu中使用了<router-link>这玩意,后来改造成  @click="router.push(ele.path)"即可消除警告 2.网络上各种方式我均尝试过,都是无效方案,比如:......
  • PAT Advanced 1003. Emergency
    PATAdvanced1003.Emergency1.ProblemDescription:Asanemergencyrescueteamleaderofacity,youaregivenaspecialmapofyourcountry.Themapshowsseveralscatteredcitiesconnectedbysomeroads.Amountofrescueteamsineachcityandthelen......
  • cpp: Template Mothod Pattern
    文章来源《C++新经典设计模式》王健伟编著 清华大学出版社 //TemplateMethonPattern.h:此文件包含"TemplateMethonPattern"类。TemplateMothodPatternC++14//2023年4月29日涂聚文GeovinDuedit.#define_UNICODE#pragmaonce#ifndefTEMPLATEMOTHOD_H......
  • 力扣---1004. 最大连续1的个数 III
    给定一个二进制数组 nums 和一个整数k,如果可以翻转最多k个0,则返回数组中连续1的最大个数。 示例1:输入:nums=[1,1,1,0,0,0,1,1,1,1,0],K=2输出:6解释:[1,1,1,0,0,1,1,1,1,1,1]粗体数字从0翻转到1,最长的子数组长度为6。示例2:输入:nums=[0,0,1,1,0,0,1,1,1,......
  • session.save_path is correct (/var/lib/php/session) in Unknown on line 0
    session.save_pathiscorrect(/var/lib/php/session)inUnknownonline0 解决办法:方法1、注释掉/etc/php.ini中session.save_path=“/var/lib/php/session”方法2、查看apache用户和组,然后将该用户加到session文件夹所处的组中。方法3,在session_start()前不要有任何输出!......
  • PATH和path,傻傻分不清
    习惯了Windows电脑下的所见即所得,找到程序或文件双击即可运行或打开;于是我们被惯得以为电脑会像人一样聪明,给他一个名字就可以运行程序或打开文件;于是在命令行下或程序里不断碰壁,为啥这个命令不运行了呢?我们不能太高估电脑(或操作系统),不要以为只要输入一个程序名或文件名,电脑(或操作......
  • 《Dashboard Design Patterns》
    今日组会分享了一篇有关可视化界面设计的论文,收获颇多,在此记录一下。论文期刊:IEEETRANSACTIONSONVISUALIZATIONANDCOMPUTERGRAPHICS,VOL.29,NO.1,JANUARy2023WhatisDashboard(可视化界面)?“Dashboard:Avisualdisplayofthemostimportantinformationneede......
  • Python关于jsonpath路径里面包含中文或进行参数化的解决方案
    jsonpath路径包含中文当jsonpath路径包含中文时,我们只需要在jsonpath路径里面把中文用引号包裹即可准备json文件{"data":[{"Details":[{"姓名":"张三"}]}......
  • 菜鸟记录:c语言实现PAT甲级1005--Spell It Right
     非常简单的一题了,但还是交了两三次,原因:对数组的理解不足;对数字和字符之间的转换不够敏感。这将在下文中细说。Givenanon-negativeinteger N,yourtaskistocomputethesumofallthedigitsof N,andoutputeverydigitofthesuminEnglish.InputSpecificatio......