一、题目

描述.png

sample.png

二、短语词汇

1. Then M lines follow, each in the format: 然后是M行，每一行的格式为.
2. For the sake of simplicity：为了简单起见.
3. The input ends with N being 0. That case must NOT be processed：输入的N如果是0的话，此种情况不做处理.

三、思路代码

1. 输出的内容为，每一层次叶子结点的个数
2. 根据所给内容设计数据结构，每个节点包含自己的level和孩子结点的序号
3. 构造这棵树
4. 使用层次遍历，访问每一个节点，并统计每一层的叶子结点个数

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 101;
//输出是统计每一层叶子结点的的个数
int res[MAX] = {0}; 
int maxlevel = 0;

//结点结构，每个节点所在层次，每个节点的孩子结点编号
struct Node{
    int level; //所在层次
    vector<int> children; //孩子结点编号
};
Node node[MAX];


//层序遍历，给每一个节点的level赋值
//在层序遍历的同时，还可以统计这一层次的节点数量
void levelOrder(int root)
{
    queue<int> q;  //辅助队列
    q.push(root) ; //根节点入队
    node[root].level = 1;
    
    //每个元素仅被访问一次
    while(!q.empty()){  //队列不空循环
        int p = q.front(); //取队头元素
        //更新最大层次
        if(node[p].level > maxlevel)
            maxlevel = node[p].level;
        int sumchilds = node[p].children.size();
        int level = node[p].level;
        //处理p节点的孩子结点
        if(sumchilds!=0){  //如果节点p有孩子，那么其孩子入队
            for(int i=0;i <sumchilds ;i++){
                int childID = node[p].children[i];
                q.push(childID);
                node[childID].level = node[p].level+1; //孩子的节点的level等于父节点的level+1
            }
        }else{ //其为叶子结点，当前层次叶子结点的数量+1
            res[level]++;
        }
        q.pop();
    }
}

int main()
{
    //构造一棵树
    int N,M; //N为节点总数，M为非叶节点总数
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++) //M个非叶节点
    {
        int ID,k; //非叶节点ID，k个孩子
        //输入ID和k，是字符类型
        scanf("%d %d",&ID,&k);
        for(int j=1;j<k+1;j++)
        {
            int child;
            scanf("%d",&child);
            //printf("%d",child);
            node[ID].children.push_back(child);
        }
    }
    //printf("%d",nl[1].children.size());
    
    //层序遍历算法，找到并记录每一层叶子结点的个数
    levelOrder(1);
    
    //输出
    for(int i=1; i<maxlevel;i++)
    {
        printf("%d ",res[i]);
    }
    printf("%d",res[maxlevel]);

    return 0;
}