深圳网络安全公司_boss直聘企业邮箱怎么注册_怎样在浏览器上找网站_网络营销章节测试答案

题目

题目大意

给定一棵树，每个节点从01到n编号，规定01为根节点，求每层叶子节点的个数。

思路

用二维数组存储树。每层叶子节点的个数，只能用dfs深度遍历，用一个数组存储所有层数的叶子节点个数。相同层数并且是叶子节点，该层叶子节点的个数加一。树的层数即树的深度。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;int n, m, deep = 0;
vector<vector<int>> v;  // 二维数组表示树
vector<int> count;  // 每层叶子节点的个数void dfs(int root, int num){if ((int)v[root].size() == 0){deep = max(deep, num);count[num]++;return;}for (int i = 0; i < (int)v[root].size(); i++){dfs(v[root][i], num + 1);}
}int main(){cin >> n >> m;v.resize(n + 1);  // 树节点的编号从1开始count.resize(n + 1);int rootId = 1;for (int i = 0; i < m; i++){int id, num;cin >> id >> num;v[id].resize(num);for (int j = 0; j < num; j++){cin >> v[id][j];}}dfs(1, 1);for (int i = 1; i <= deep; i++){cout << count[i];if (i != deep){cout << " ";}}cout << endl;return 0;
}