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

PAT Advanced 1004 Counting Leaves

2021-01-23 18:43:33 itread01

# 題目與翻譯## 1004 Counting Leaves 數樹葉 (30分)A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.一個家族的等級通常是由一個系譜樹表示的。你的工作是統計那些沒有孩子的家庭成員。### 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:每個輸入檔案包含一個測試用例。每個案例都從一行開始,該行包含0 < n < 100、樹中節點的數量和 m (< n)、非葉節點的數量。然後是 m 行,每行格式如下:```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`.其中 ID 是表示給定非葉節點的兩位數,k 是其子節點的數量,後面是其子節點的兩位數 ID 序列。為了簡單起見,讓我們將根 ID 修改為01。The input ends with *N* being 0. That case must NOT be processed.輸入結束時 n 為0。這種情況不能被處理。### 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.示例案例表示一個只有2個節點的樹,其中01是根,02是它的唯一子節點。因此,在根01級上,有0個葉節點; 在下一級上,有1個葉節點。那麼我們應該在一行中輸出01。### Sample Input:### 樣本輸入:```in2 101 1 02```### Sample Output:### 示例輸出:```out0 1```# 理解與演算法簡單地講,這道題就是在求一棵多叉樹的葉子節點的數量,並按照層的順序列印!如果沒有葉子結點就列印0,否則輸出葉子結點個數。粗略地想一想,層序遍歷和前序遍歷都可以完成,這裡用的是深度優先演算法,也就是先序遍歷。給出一個樣例的示意圖:![image-20210123123245154](https://img.tanknee.cn/blogpicbed/2021/01/23/2021012319ada2d3da37b.png)`01`是根節點,因為它有一個子節點`02`所以它不是葉子結點,而`02`是葉子結點,因此最後的輸出為:```out0 1```接下來來實現程式。### 處理輸入```c++// 全域性變數vector nodes[100]; // 每個元素代表一個節點連結串列int pedigree[100]; // 族譜樹中每一層的葉子結點的數量int pedigree_depth = -1; // 族譜樹的最大深度int main...(省略部分)int N, M, node, num, child;// 處理第一行cin >> N >> M;// 遍歷所有的非葉節點,構建節點連結串列for (int i = 0; i < M; ++i) { cin >> node >> num; for (int j = 0; j < num; ++j) { cin >> child; nodes[node].push_back(child); }}```這裡用了一個vector的陣列來儲存每個節點的子節點連結串列。### 遍歷族譜樹```c++/** * 深度優先演算法,遍歷整個家族樹,如果找到葉子結點就加入到全域性變數陣列中 * @param index 下標 * @param depth 深度 */void dfs(int index, int depth) { if (nodes[index].empty()) { // 如果這個節點沒有子節點,那麼就是葉子結點 pedigree[depth]++; // 這個葉子結點的深度如果超過原本記錄的最大深度,那麼就更新最大深度 pedigree_depth = depth > pedigree_depth ? depth : pedigree_depth; return; } // 遍歷該節點的所有子節點 for (int i : nodes[index]) { // 因為往下走了一層,所以深度加1 dfs(i, depth + 1); }}```為了提高效率,不用每次都遍歷整個族譜葉子個數的陣列,我們可以使用一個全域性變數`pedigree_length`來確定整個陣列的長度,提高最後的列印效率。### 輸出```c++// 陣列預設值為0,這裡輸出這個陣列的全部內容,長度為pedigree_lengthcout << pedigree[0];for (int i = 1; i <= pedigree_depth; ++i) { cout << " " << pedigree[i];}```## 程式碼實現```c++#include #include using namespace std;vector nodes[100]; // 每個元素代表一個節點連結串列int pedigree[100]; // 族譜樹中每一層的葉子結點的數量int pedigree_depth = -1; // 族譜樹的最大深度/** * 深度優先演算法,遍歷整個家族樹,如果找到葉子結點就加入到全域性變數陣列中 * @param index 下標 * @param depth 深度 */void dfs(int index, int depth) { if (nodes[index].empty()) { // 如果這個節點沒有子節點,那麼就是葉子結點 pedigree[depth]++; // 這個葉子結點的深度如果超過原本記錄的最大深度,那麼就更新最大深度 pedigree_depth = depth > pedigree_depth ? depth : pedigree_depth; return; } // 遍歷該節點的所有子節點 for (int i : nodes[index]) { // 因為往下走了一層,所以深度加1 dfs(i, depth + 1); }}int main() { int N, M, node, num, child; // 處理第一行 cin >> N >> M; // 遍歷所有的非葉節點,構建節點連結串列 for (int i = 0; i < M; ++i) { cin >> node >> num; for (int j = 0; j < num; ++j) { cin >> child; nodes[node].push_back(child); } } // 對族譜樹進行深度優先遍歷 dfs(1, 0); // 陣列預設值為0,這裡輸出這個陣列的全部內容,長度為pedigree_length cout << pedigree[0]; for (int i = 1; i <= pedigree_depth; ++i) { cout << " " << pedigree[i]; } return 0

版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1611391744.html

随机推荐