1004. Counting Leaves（30）—PAT 甲級

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

題目大意：計算樹的每一層上有多少個葉子節點並按層輸出
分析：使用深度有限搜索（DFS）遞歸遍歷樹上每一個節點的孩子節點，如果這個節點沒有孩子節點，就逐層返回。child[i]集合記錄每個節點的孩子節點，leaf[i]數組記錄每一層上的葉子節點，max_h記錄最大層數，層數從1開始。也可以使用廣度優先搜索（BFS）,不同之處是DFS使用集合，BFS使用隊列，且BFS不用使用遞歸，只需要第一個節點入隊列後判斷隊列非空即可。

//DFS求葉子節點
#include <iostream>
#include <vector>
using namespace std;
int leaf[100],max_h=1;
vector<int> child[100];
void DFS(int id_num,int h)
{
    if(max_h<h) max_h=h;
    int k=child[id_num].size();
    if(k==0){
        leaf[h]+=1;
        return;
    }
    for(int i=0;i<k;i++)
    {
        DFS(child[id_num][i],h+1);
    }
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    int id_num,k,id;
    for(int i=0;i<m;i++){
        scanf("%d %d",&id_num,&k);
        for(int j=0;j<k;j++){
            scanf("%d",&id);
            child[id_num].push_back(id);
        }
    }
    DFS(1,1);
    for(int i=1;i<=max_h;i++){
        if(i!=1) printf(" ");
        printf("%d",leaf[i]);
    }
    printf("\n");
    return 0;
}