AcWing 1476. 数叶子结点
原题链接
简单
作者:
mkuiwu
,
2021-01-19 21:20:09
,
所有人可见
,
阅读 318
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
// 模拟邻接表
int h[N], e[N], ne[N], idx;
// 把树 看成邻接表, 确实是可以的, 而且得开n个数组
// 因为最坏的情况下, 每个节点只有一个孩子, 变成单链表形式, 需要h[n] 个空间来存储
// 添加函数
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 根据题意 需要记录每层的叶子节点数量
int cnt[N], max_depth; // 用来记录最大深度
int n, m;
// 需要两种数据, 1、 当前根节点 2、 当前深度
void dfs(int u, int cur_depth){
// 先写好返回条件
if(h[u] == -1){ // 如果是叶子节点, 则可以直接返回了
cnt[cur_depth]++;
// 更新一下最大值
max_depth = max(cur_depth, max_depth);
return;
}
// 如果不是叶子节点则需要遍历一下子节点
for(int i = h[u]; i != -1; i = ne[i]){
dfs(e[i], cur_depth + 1);// 而且得从e[i] 中取值继续执行, 并且深度加一
}
}
int main(){
// memset一般只能用来初始化 char, 对于 int 只能初始化成 -1 or 0
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--)
{
int id, k, b;
cin >> id >> k;
while(k--){
cin >> b;
add(id, b);
}
}
// 深度倒是无所谓, 可以直接从 0开始
dfs(1, 0);
cout << cnt[0];
for(int i = 1; i <= max_depth; i++)
cout << ' ' << cnt[i];
cout << endl;
return 0;
}