PAT A1004 Counting Leaves

清疚 2021-09-29 07:48 262阅读 0赞

本程序为PAT A1004 Counting Leaves答案，[题目链接][Link 1]。

**主体思想：**算法主要采用DFS算法，深度优先访问每一个结点，检查其是否为叶子结点。

**详细介绍：**

使用向量容器vector存储每个结点的所有孩子结点：*v\[ID\].push\_back(temp)*;

使用数组*num\[\]*记录每层的叶子结点数量；

使用深度优先搜索算法DFS，采用递归的方式，每次向深处前进时*depth++*,回退时*depth--*;访问到某个结点时，若其无孩子，*num\[depth\]++*; 遍历结束时，可以得到所有层的num\[depth\];

使用*maxdepth*变量抓取在整个递归过程中最大的depth;

**注意：**

使用递归方式实现DFS算法，容易忘记回退时将增量减掉。

**程序代码：**

1 #include "pch.h"
     2 #include <iostream>
     3 #include <vector>
     4 using namespace std; 5 
     6 const int MAXN = 100; 7 int num[MAXN];//记录每行有多少个叶子
     8 int maxdepth=0;//抓最大深度
     9 vector<int>v[MAXN];//存储每个顶点的所有叶子
    10 
    11 void DFS(int depth,int index) { 12     if (v[index].size() == 0) { 13         num[depth]++; 14 } 15     for (int i = 0; i < v[index].size(); i++) { 16         depth++; 17         if(depth> maxdepth)maxdepth = depth;//抓取最大深度
    18 DFS(depth,v[index][i]); 19         depth--;//递归回退时别忘记消除增量！
    20 } 21 } 22 int main() 23 { 24     int n, m,ID, K,temp; 25     cin >> n >> m; 26     fill(num, num + n, 0);//num存储每层叶子数，初始化为0
    27     if (n < 1)return 0; 28     for (int i = 0; i < m; i++) {
         //M行依次录入
    29         cin >> ID >> K; 30         for (int i = 0; i < K; i++) { 31             cin >> temp; 32 v[ID].push_back(temp); 33 } 34 } 35     DFS(0,1); 36     for (int i = 0; i < maxdepth; ++i) { 37         cout << num[i] << ' '; 38 } 39     cout << num[maxdepth]; 40 }

**提交结果：**

![1526692-20190521230429538-67385224.png][]

转载于:https://www.cnblogs.com/qujunhui/p/10903146.html

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184
[1526692-20190521230429538-67385224.png]: /images/20210725/cb43a0d03f69453bb37edc99d6506016.png