点击链接PAT甲级-AC全解汇总
题目：
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.
Sample Input:
2 1
01 1 02
Sample Output:
0 1
题意：
第一行输入节点数（貌似没啥用） 和所有父节点数，也就是之后输入的行数
然后每行输入当前节点编号 他的子节点数 和一系列子节点
输出要求是输出每层有多少个叶节点
我的代码：
#include<bits/stdc++.h>
using namespace std;struct node{
int level;//好像没什么用vector<int>sons;
}all_father[120];
int max_level=0;
int level_nonleaf[120]={
0};void DFS(int father,int level)
{
all_father[father].level=level;if(all_father[father].sons.size()==0){
level_nonleaf[level]++;return;}level++;max_level=max(max_level,level);for(int i=0;i<all_father[father].sons.size();i++){
DFS(all_father[father].sons[i],level);}
}int main()
{
int N,M;cin>>N>>M;for(int i=0;i<M;i++)//M行，每行以父节点开头，它的子随后{
int father_id,num_son;cin>>father_id>>num_son;for(int j=0;j<num_son;j++){
int son;cin>>son;all_father[father_id].sons.push_back(son);}}DFS(1,0);for(int i=0;i<=max_level;i++){
cout<<level_nonleaf[i];if(i!=max_level)cout<<" ";}return 0;
}注意： 输入不一定是根节点开头，一开始做错了，仔细读题发现固定root的id为01，如果输入第一个父节点不是01的话，就没办法直接计算层号了，所以得先把所有数据输入之后在进行统计
如果输入是按照层输入的话，可以用下面的代码：
#include<bits/stdc++.h>
using namespace std;int main()
{
int N,M;cin>>N>>M;int node_level[500]={
0};//每个结点自己在第几层int level_nonleaf[500]={
0};int max_level=1;for(int i=0;i<M;i++)//M行，每行以非叶结点开头，它的子随后{
int id_father,num_son,level_son=2;//root,当作第一层cin>>id_father>>num_son;if(i!=0)//不是第一层,子节点都为（父+1）层{
int level_father=node_level[id_father];level_nonleaf[level_father]--;//父层叶节点个数-1level_son=level_father+1;}max_level=level_son>max_level?level_son:max_level;//记录层数，方便输出level_nonleaf[level_son]+=num_son;//子层叶节点个数加上子数for(int j=0;j<num_son;j++)//k个子节点{
int id_son;cin>>id_son;node_level[id_son]=level_son;}}//逐层输出多少个叶节点；for(int i=1;i<=max_level;i++){
cout<<level_nonleaf[i];if(i!=max_level)cout<<" ";}return 0;
}