当前位置:网站首页>PAT Advanced 1004 Counting Leaves

PAT Advanced 1004 Counting Leaves

2021-01-23 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 non-leaf 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 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`. 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 :![image-20210123123245154](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

随机推荐