PAT A1004 Counting Leaves 清疚 2021-09-29 07:48 158阅读 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
还没有评论,来说两句吧...