原题目

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

题目大意

给定一棵树，求这棵树每层分别有多少个叶子结点。
输入的第一行是N和M两个整数，分别代表树的总结点数和总的非叶子结点数。之后的M行每行按照如下格式输入：

ID K ID[1] ID[2] ... ID[K]

其中ID是一个两位数的数字，代表一个非叶子结点；K代表该非叶子结点的孩子的个数，后面的K个两位数的ID代表这个结点的孩子。为方便起见，树的根节点定为ID为01的结点。

题解

将输入的内容保存到结构体数组中，根结点的深度置为0，然后加入队列，用BFS进行搜索。
从队首取出顶点，判断是否有孩子，若没有，则将该深度下的叶子结点数加1；若有孩子，则遍历其所有孩子，每个孩子的深度设为当前结点的深度加1，然后加入队列。

C语言代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define true 1
#define false 0
#define max(a, b) (a) > (b) ? (a) : (b)
#define element_type int
#define INF -2147483648

/*---------------队列模板start----------*/
typedef struct Queue_element{
    element_type val;
    struct Queue_element *next;
}queue_element;

typedef struct Queue{
    queue_element *front;    
    queue_element *rear;
}queue_t;

int is_empty(queue_t* queue){
    if(!queue->front || !queue->rear)
        return 1;
    else
        return 0;
}

element_type dequeue(queue_t* queue){
    if(is_empty(queue))
        return INF;
    else{
        element_type ret = queue->front->val;
        queue_element* tmp = queue->front;
        queue->front = tmp->next;
        free(tmp);
        return ret;
    }
}

void enqueue(queue_t* queue, element_type num){
    queue_element* new_element = (queue_element*) malloc(sizeof(queue_element));
    new_element->next = NULL;
    new_element->val = num;
    if(is_empty(queue)){
        queue->front = new_element;
        queue->rear = new_element;
        return;
    }
    queue->rear->next = new_element;
    queue->rear = new_element;
}

queue_t* create_empty_queue(){
    queue_t* ret = (queue_t*) malloc(sizeof(queue_t));
    ret->front = NULL;
    ret->rear = NULL;
    return ret;
}
/*---------------队列模板end------------*/

typedef struct TREE_NODE{
    char children_num;  //当前结点的孩子数目
    char *children;     //存储当前结点的孩子
    char depth;         //存储当前结点的深度
}tree_node;

int main(){
    int depth = 0;
    tree_node *node = malloc(sizeof(tree_node) * 101);
    for(int i = 0;i < 101;++i){
        node[i].children_num = 0;
        node[i].children = NULL;
        node[i].depth = 101;
    }
    int m, n;
    scanf("%d %d", &n, &m);
    for(int i = 0;i < m;++i){
        int index;
        scanf("%d", &index);
        scanf("%d", &node[index].children_num);
        node[index].children = malloc(node[index].children_num);
        for(int j = 0;j < node[index].children_num;++j){
            scanf("%d", node[index].children + j);
        }
    }
    node[1].depth = 0;
    char *leaf_node_nums = malloc(sizeof(char) * n);
    memset(leaf_node_nums, 0, sizeof(char) * n);

    queue_t *queue = create_empty_queue();
    enqueue(queue, 1);
    while(!is_empty(queue)){
        int current = dequeue(queue);
        if(!node[current].children_num){
            leaf_node_nums[node[current].depth]++;
            continue;
        }
        for(int i = 0;i < node[current].children_num;++i){
            enqueue(queue, node[current].children[i]);
            node[node[current].children[i]].depth = node[current].depth + 1;
            depth = max(depth, node[node[current].children[i]].depth);
        }
    }

    for(int i = 0;i <= depth;++i){
        if(i == depth)
            printf("%d\n", leaf_node_nums[i]);
        else
            printf("%d ", leaf_node_nums[i]);
    }
    return 0;
}

一开始写的时候是直接在输入的时候将孩子结点的深度设为父结点深度加1，但是这样只能过两个点，说明输入的用例中有的结点是先于它的父结点出现的。要计算当前结点的深度还是只能用BFS搜一遍。（害得我又重新写了一个队列模板）