PAT-A 1004. Counting Leaves (30) (树)

本文主要是介绍PAT-A 1004. Counting Leaves (30) (树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://www.patest.cn/contests/pat-a-practise/1004

题意：

样例

输入：

2 1

01 1 02

输出：

0 1

第一行一共n个节点，其中非叶子节点有m个，下面m行，每行第一个数id是当前结点编号，第二个数k是当前结点有多少个孩子，后面k个数都是孩子的编号。

要求按顺序输出每一层的叶子节点的数量。

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct node {int num; //该节点的孩子数 vector<int> child; //孩子的序号 
};
node T[110];
int ans[110], mh; //ans[i]表示第i层上有多少个叶子
//mh表示最大的层数 
void count_leaves(node rt, int h) { //参数rt表示当前节点，h表示当前结点层数 mh = mh < h ? h : mh; //不断维护层数的最大值 if(rt.num == 0) ans[h]++;   else {int i, j;for(i = 0; i < rt.child.size(); i++) {count_leaves(T[rt.child[i]], h + 1); //非叶子结点则递归判断 }}
}
int main() {int n, m;scanf("%d %d", &n, &m);int i, j, k, id, cd;for(i = 0; i < m; i++) {scanf("%d %d", &id, &k);T[id].num = k; // 以下标表示节点号 for(j = 0; j < k; j++) {scanf("%d", &cd);T[id].child.push_back(cd);}}count_leaves(T[1], 0);for(i = 0; i <= mh; i++) {if(i == 0) printf("%d", ans[i]);else printf(" %d", ans[i]);}printf("\n");return 0;
}

这篇关于PAT-A 1004. Counting Leaves (30) (树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---