# 甲级 PAT1004 Counting Leaves

1004 Counting Leaves (30)（30 分）

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input

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.

Output

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<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define maxsize 101

int tree[maxsize];
int leaf[maxsize];
int maxnode[maxsize];
int level = 1;

int main(){
int N,M,root,node,K,i,max;
cin>>N>>M;
if(N == 1){
cout<<1;
}else{
//初始化数组
memset(tree,0,sizeof(tree));
memset(leaf,0,sizeof(leaf));
memset(maxnode,0,sizeof(node));
//输入数据
while(M--){
cin>>root>>K;
while(K--){
cin>>node;
tree[node] = root;
}
}
//核心实现
queue<int> q;
q.push(1);
maxnode[0] = 1;
while(!q.empty()){
node = q.front();
max = 0;
for(i=1;i<100;i++){
if(tree[i] == node){
q.push(i);
max = i;
}
}
if(max == 0){
leaf[level]++;
}else{
maxnode[level] = max;
}
q.pop();
if(node == maxnode[level-1]){
level++;
}
}
//输出
for(i=1;i<level;i++){
if(i<level-1){
cout<<leaf[i]<<" ";
}else{
cout<<leaf[i];
}
}
}

return 0;
} ``````

# 注意：

1.这里判断每一层结束了的条件是：该结点==上一层最后一个结点加入队列中的子结点。也就是代码中的if(node == maxnode[level-1])

2.代码中的max判断该结点node是否为叶结点也为后面将每层加入队列中的最后一个非叶结点的ID记录下来。因为若所有的结点都没有对应的父结点tree[i]等于node，那么该node一定是叶结点

3.要注意maxnode中存放的每层加入队列中的最后一个非叶结点的ID。之前直接把maxnode[level] = max;写在了判断每层结束的条件里，因为想着最后一个结点对应的最后一个子结点max就是每层加入队列中的最后一个非叶结点的ID，但是，忽略了最后一个结点可能是一个非叶结点。因此在刚开始写完有一个始终不通过。

4.特例像树只有一个结点（N=1）的时候直接输出1即可

5.int a=01;不会报错，输出结果为1