题目
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];
}
