PAT甲级1004题（数叶子节点）

二叉树题

PAT

发布日期: 2021-02-23

文章字数: 186

阅读时长: 1 分

阅读次数:

1.题目介绍

1004

2.考察点，难度

二叉树类，邻接表存储，深度搜索，难度中

3.解题代码

#include <bits/stdc++.h>
using namespace std;

const int N=110;
int h[N],e[N],ne[N],idx;
int m,n,max_depth,cnt[N];

void add(int a, int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u, int depth){
    if(h[u]==-1){
        max_depth=max(max_depth,depth);
        cnt[depth]+=1;
    }else{
        for(int i=h[u];~i;i=ne[i])
            dfs(e[i],depth+1);
    }
}

int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while(m--){
        int now,sum;
        cin>>now>>sum;
        while(sum--){
            int cn;
            cin>>cn;
            add(now,cn);
        }
    }
    dfs(1,0);
    cout<<cnt[0];
    for(int i=1;i<=max_depth;i++)    cout<<" "<<cnt[i];
    cout<<endl;
    return 0;
}