PAT甲题题解-1004. Counting Leaves (30)-统计每层叶子节点个数+dfs

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
/*
统计每层的叶子节点个数
建树，然后dfs即可
*/
const int maxn=;
int n,m;
int layer[maxn]; //统计每层的叶子节点个数
int maxlayer=;
vector<int>node[maxn];void dfs(int u,int level){
int num=node[u].size();
if(num==){
layer[level]++;
if(level>maxlayer)
maxlayer=level;
return;
}
for(int i=;i<node[u].size();i++){
dfs(node[u][i],level+);
}
}
int main()
{
memset(layer,,sizeof(layer));
scanf("%d %d",&n,&m);
int u,v,k;
for(int i=;i<m;i++){
scanf("%d %d",&u,&k);
for(int i=;i<k;i++){
scanf("%d",&v);
node[u].push_back(v);
}
}
dfs(,);
printf("%d",layer[]);
for(int i=;i<=maxlayer;i++)
printf(" %d",layer[i]);
return ;
}