PAT A1004

刺骨的言语ヽ痛彻心扉 2022-03-07 00:20 167阅读 0赞

![clipboard.png][]

还是数层数和数节点的问题，个人觉得用BFS比较好；  
当然用DFS也能做，具体的思路就是建立层数数组，深度遍历到x层的时候，如果是叶子节点就leaf\[x\]++，如果不是就不管，继续跳过；  
代码片段可以这样：

void DFS(int index,int h){
        max_h=max(h,max_h);
        if(G[index].size()==0){
            leaf[h]++;
            return;
        }
        for(int i=0;i<G[index].size();i++){
            DFS(G[index][i],h+1);
        }
    }

BFS代码如下所示：

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<vector>
    #include<queue>
    using namespace std;
    using std::vector;
    using std::queue;
    const int maxn=110;
    int n,m;
    int leaf[maxn]={0};//每层leaf个数
    vector<int> table[maxn];
    int BFS(int x){
        int layer=0;
        queue<int>q;
        q.push(x);
        while(!q.empty()){
            int num=0;
            int length=q.size();
            layer++;
            for(int i=0;i<length;i++){
                int id=q.front();
                q.pop();
                if(table[id].size()==0){
                    num++;
                }
                for(int j=0;j<table[id].size();j++){
                    q.push(table[id][j]);
                }
            }
            leaf[layer]=num;
        }
        return layer;
    }
    int main(){
        int root,l,num;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d %d",&root,&num);
            for(int j=0;j<num;j++){
                scanf("%d",&l);
                table[root].push_back(l);
            }
        }
        int layer=BFS(1);
        for(int i=1;i<=layer;i++){
            if(i==1)
                printf("%d",leaf[i]);
            else
                printf(" %d",leaf[i]);
        }
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20220307/73b8dadb63c34082a21ad4a7887a4ac2.png