当前位置：网站首页>PAT Advanced 1004 Counting Leaves
PAT Advanced 1004 Counting Leaves
20210123 18:45:41 【itread01】
# Title and translation ## 1004 Counting Leaves Count the leaves (30 branch )A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. The hierarchy of a family is usually represented by a family tree . Your job is to count family members who don't have children .### Input Specification:### Input specifications :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 nonleaf nodes. Then *M* lines follow, each in the format: Each input file contains a test case . Each case starts with one line , This line contains 0 < n < 100、 The number of nodes in the tree and m (< n)、 The number of non leaf nodes . And then there was m That's ok , The format of each line is as follows :```ID K ID[1] ID[2] ... ID[K]```where `ID` is a twodigit number representing a given nonleaf node, `K` is the number of its children, followed by a sequence of twodigit `ID`'s of its children. For the sake of simplicity, let us fix the root ID to be `01`. among ID Is a two digit number representing a given non leaf node ,k Is the number of its child nodes , Followed by the two digits of its child node ID Sequence . For the sake of simplicity , Let's take root ID It is amended as follows 01.The input ends with *N* being 0. That case must NOT be processed. At the end of the input n For 0. This situation cannot be dealt with .### Output Specification:### 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. For each test case , You should calculate the qualifications of family members who have no children at all . The numbers have to be printed on one line , Separated by a space , And there must be no extra spaces 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. The example case shows a case with only 2 A tree of nodes , among 01 It's a root ,02 Is its only child node . therefore , At the root 01 On the level of , Yes 0 Leaf nodes ; At the next level , Yes 1 Leaf nodes . So we should output in one line 01.### Sample Input:### Sample input :```in2 101 1 02```### Sample Output:### Sample output :```out0 1```# Understanding and algorithms, in short , This problem is to find the number of leaf nodes of a multi tree , And print in the order of layers ！ If there is no leaf node, print 0, Otherwise, output the number of leaf nodes . Think about it roughly , Sequence traversal and preorder traversal can be completed , This is a depth first algorithm , That is, preorder traversal . Give a schematic diagram of an example ：![image20210123123245154](https://img.tanknee.cn/blogpicbed/2021/01/23/2021012319ada2d3da37b.png)`01` It's the root node , Because it has a child node `02` So it's not a leaf node , and `02` It's a leaf node , So the final output is ：```out0 1``` Next, let's implement the program .### Processing input ```c++// Global variable vector
nodes[100]; // Each element represents a list of node Links int pedigree[100]; // The number of leaf nodes in each layer of the tree int pedigree_depth = 1; // The maximum depth of the genealogy tree int main...( Omit the part )int N, M, node, num, child;// Deal with the first line cin >> N >> M;// Traverse all non leaf nodes , Build a list of node Links for (int i = 0; i < M; ++i) { cin >> node >> num; for (int j = 0; j < num; ++j) { cin >> child; nodes[node].push_back(child); }}``` Here's a vector Array to store the child node connection string of each node .### Traverse the genealogy tree ```c++/** * Depth first algorithm , Traverse the entire family tree , If the leaf node is found, it is added to the global variable array * @param index Subscript * @param depth depth */void dfs(int index, int depth) { if (nodes[index].empty()) { // If this node has no children , That's the leaf node pedigree[depth]++; // If the depth of this leaf node exceeds the maximum recorded depth , Then update the maximum depth pedigree_depth = depth > pedigree_depth ? depth : pedigree_depth; return; } // Traverse all the children of the node for (int i : nodes[index]) { // Because it goes down one level , So depth plus 1 dfs(i, depth + 1); }}``` In order to improve efficiency , You don't have to traverse the array of leaves in the whole genealogy every time , We can use a global variable `pedigree_length` To determine the length of the entire array , Improve the final printing efficiency .### Output ```c++// The array default is 0, Here's the output of the entire array , The length is pedigree_lengthcout << pedigree[0];for (int i = 1; i <= pedigree_depth; ++i) { cout << " " << pedigree[i];}```## Code implementation ```c++#include
#include
using namespace std;vector
nodes[100]; // Each element represents a list of node Links int pedigree[100]; // The number of leaf nodes in each layer of the tree int pedigree_depth = 1; // The maximum depth of the genealogy tree /** * Depth first algorithm , Traverse the entire family tree , If the leaf node is found, it is added to the global variable array * @param index Subscript * @param depth depth */void dfs(int index, int depth) { if (nodes[index].empty()) { // If this node has no children , That's the leaf node pedigree[depth]++; // If the depth of this leaf node exceeds the maximum recorded depth , Then update the maximum depth pedigree_depth = depth > pedigree_depth ? depth : pedigree_depth; return; } // Traverse all the children of the node for (int i : nodes[index]) { // Because it goes down one level , So depth plus 1 dfs(i, depth + 1); }}int main() { int N, M, node, num, child; // Deal with the first line cin >> N >> M; // Traverse all non leaf nodes , Build a list of node Links for (int i = 0; i < M; ++i) { cin >> node >> num; for (int j = 0; j < num; ++j) { cin >> child; nodes[node].push_back(child); } } // Depth first traversal of the genealogy tree dfs(1, 0); // The array default is 0, Here's the output of the entire array , The length is pedigree_length cout << pedigree[0]; for (int i = 1; i <= pedigree_depth; ++i) { cout << " " << pedigree[i]; } return 0
版权声明
本文为[itread01]所创，转载请带上原文链接，感谢
https://chowdera.com/2021/01/20210123184315033P.html
边栏推荐
 Podinfo，迷你的 Go 微服务模板
 Podinfo，迷你的 Go 微服务模板
 【高频讨论】青春饭的程序员！35 岁面临被优化，你会害怕吗？
 Service package for patient management
 Podinfo, mini go microservice template
 Memcached 缓存数据库应用实践
 Podinfo, mini go microservice template
 關於SQL Server 映象資料庫快照的建立及使用
 [high frequency discussion] programmer of youth meal! Are you afraid of being optimized at 35?
 別再問我們用什麼畫圖的了！問就是excalidraw
猜你喜欢

ABP vNext 實現租戶Id自動賦值插入

C++ STL list

Application practice of memcached cache database

On the establishment and use of SQL Server image database snapshot

Don't ask us what we draw with! The question is excalidraw

ABP vNext realizes automatic assignment and insertion of tenant ID

C++ STL list

KubeSphere and Friends 2020 落幕 与开源社区伙伴零距离、全方位解读云原生

Qt跨平台编程之中文编码问题

Go  统一定义 API 错误码
随机推荐
 混合云一站式运维监控滴滴夜莺
 Go  基于 GORM 获取当前请求所执行的 SQL 信息
 KubeSphere and Friends 2020 落幕 与开源社区伙伴零距离、全方位解读云原生
 Kubesphere and friends 2020 comes to an end
 Chinese coding in QT cross platform programming
 Go  unified definition API error code
 One stop operation and maintenance monitoring of hybrid cloud  didi Nightingale
 Go  get the SQL information of the current request based on Gorm
 Kubesphere and friends 2020 comes to an end
 7年沉淀之作滴滴Logi日志服务套件
 Didi log service Suite
 我在服务器上执行了 rm rf *
 I executed RM  RF on the server*
 STL简介
 Introduction to STL
 es6语法详解
 STL_string容器
 Detailed explanation of ES6 grammar
 STL_ String container
 STL_vector容器
 es6语法详解
 STL_string容器
 STL_ Vector container
 Detailed explanation of ES6 grammar
 STL_ String container
 一个程序员的自述
 A programmer's account
 缓存IO和直接IO
 Cache IO and direct IO
 渗透测试中期漏洞复现MS08_067
 Mid penetration test  vulnerability recurrence  MS08_ 067
 面经手册 · 第27篇《JVM 判断对象已死，实践验证GC回收》
 Chapter 27 "JVM judge object is dead, practice verification GC recovery"
 渗透测试中期漏洞复现MS08_067
 日常分享：关于时间复杂度和空间复杂度的一些优化心得分享(C＃)
 Mid penetration test  vulnerability recurrence  MS08_ 067
 Daily sharing: some optimization experience sharing about time complexity and space complexity (c)
 WebView brings photos and videos to the end
 怎样才能和编程语言对上眼？你需要做些准备以及...
 How to match programming language? You need to do some preparation and