PAT 1004. 数叶子结点
原题链接
简单
作者:
YAX_AC
,
2024-11-28 16:51:19
,
所有人可见
,
阅读 5
//hierarchy等级制度 pedigree家谱 a two-digit number一个两位数字
//For the sake of simplicity为了简单起见 processed处理
//seniority资历年长级别高
//A family hierarchy is usually presented by a pedigree tree.
//家族等级通常由家谱树表示。
//The input ends with N being 0.That case must NOT be processed
//输入以N为0结束。该案件不得处理
// you are supposed to count those family members who have no child for every seniority level starting from the root.
//从根结点开始,自上到下,树的每一层级分别包含多少个叶子节点。
//没有儿子的节点就是叶子节点
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int n,m;
int h[N],e[N],ne[N],idx;
int cnt[N],max_depth;
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u,int depth)//u是节点编号,depth是层数
{
if(h[u]==-1)//说明是叶子节点
{
cnt[depth]++;
max_depth = max(max_depth,depth);//最大层数
return;
}
//遍历子节点
for(int i = h[u]; i!=-1; i = ne[i])
dfs(e[i],depth+1);
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i = 0; i<m; i++)
{
int id,k;
cin>>id>>k;
while(k--)
{
int son;
cin>>son;
add(id,son);
}
}
dfs(1,0);
cout<<cnt[0];
for(int i = 1; i<=max_depth; i++) cout<<' '<<cnt[i];
return 0;
}