题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184

解法

输入一个树，输出树每层的子节点数目（节点1始终为根）
树输入时不按自顶向下顺序，乱序输入。因此无法建树时确定每个节点所在层数
因此建树时只需要保存每个节点的子节点信息，利用dfs层序遍历即可
推荐按照树的数据结构存储，这样dfs代码简介

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<vector<int>> tree;
int N, M;
vector<int> res;

void dfs()
{
    queue<int> q;
    int laynum;  // 每层节点数
    int emptnum;   // 每层子节点数
    q.push(1); 
    while(!q.empty())
    {
        laynum = q.size();
        emptnum = 0;
        while(laynum--)     // 遍历当前层
        {
            int fnt = q.front();
            if(tree[fnt].empty())  //  每层的节点判断是否为子节点 
                emptnum++;  
            else 
            {
                for(auto& ch : tree[fnt])  // 非子节点则将其子节点加入下一层
                    q.push(ch);
            }
            q.pop();
        }
        res.push_back(emptnum);
    }
}

int main()
{
    cin >> N >> M;
    if(N == 0) return 0;
    tree.reserve(N+1);
    for(int i = 0; i < M; i++)
    {
        int node, k;  cin >> node >> k;
        for(int j = 0; j < k; j++)
        {
            int child;  cin >> child;
            tree[node].push_back(child);
        }
    }
    dfs();
    cout << res[0];
    for(int i = 1; i < res.size(); i++)
        cout << " " << res[i];
}