1004 Counting Leaves

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

1	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:

1 2	2 1 01 1 02

Sample Output:

0 1

浅析

Q：问一棵树每一层有多少个叶子节点

此题与 A1094 极为类似，同样给出 DFS 和 BFS 两种方法。A1094 要求计算每一层结点数并寻找最大值，而本题要求输出每一层的叶子节点数，因此只需在 DFS 增加结点数处做改动。同时，因为要输出每一层的非叶子节点数，之前初始化节点数数组为 0 的方法不再适用，要维持一个最大深度变量。

Code

DFS

#include 
#include 
#include 
using namespace std;
const int maxn = 109;
int num[maxn] = {0};
vector<int> G[maxn];
int max_depth = -1;
void dfs(int s,int depth){
    if(G[s].size()==0){
        num[depth]++;
        max_depth = max(depth, max_depth);
    }
    for (int i = 0; i < G[s].size();i++){
        int v = G[s][i];
        dfs(v, depth + 1);  //这是一棵树，所以不需要vis数组
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < m;i++){
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k;j++){
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    dfs(1, 0);
    for (int i = 0; i <=max_depth; i++){< span>
        printf("%d", num[i]);
        if (i < max_depth)
            printf(" ");
    }
    return 0;
}

BFS

#include 
#include 
#include 
using namespace std;
const int maxn=109;
int level[maxn], num[maxn] = {0};
int depth = 0;
vector<int> G[maxn];
queue<int> q;

void bfs(){
    q.push(1);
    level[1] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size();i++){
            int v = G[u][i];
            level[v] = level[u] + 1;
            depth = max(level[v], depth);
            if(G[v].size()==0)
                num[level[v]]++;
            q.push(v);
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < m;i++){
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k;j++){
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    if(G[1].size()==0)
        num[0] = 1;
    else num[0] = 0;
    bfs();
    for (int i = 0; i <=depth; i++){< span>
        printf("%d", num[i]);
        if (i < depth)
            printf(" ");
    }
    return 0;
}