BFS | 1004 Counting Leaves （30 p

1004 Counting Leaves

第一次做30分题，一遍ac，快乐。
思路是bfs算层数（就是无权重路径长度）。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N=110;
vector<int> node_child[N];
int node_num,non_leaf_num;
int level[N],max_level;
vector<int> level_map[N];
//calc level
void bfs(){
    int root=1;
    max_level=level[root]=0;
    for (int i=0;i<N;i++)
        level_map[i].clear();
    level_map[level[root]].push_back(root);
    queue<int> q;
    q.push(root);
    while (!q.empty()){
        int curr=q.front();
        q.pop();
        for (int i = 0; i < node_child[curr].size(); ++i) {
            int child=node_child[curr][i];
            max_level=level[child]=level[curr]+1;
            q.push(child);
            level_map[max_level].push_back(child);
        }
    }
}
int main() {
    while (scanf("%d",&node_num)!=EOF){
        if(node_num==0)
            break;
        scanf("%d",&non_leaf_num);
        int u,cnt,v;
        for (int i=1;i<=node_num;i++)
            node_child[i].clear();
        for (int i = 0; i < non_leaf_num; ++i) {
            scanf("%d%d",&u,&cnt);
            for (int j = 0; j < cnt; ++j) {
                scanf("%d",&v);
                node_child[u].push_back(v);
            }
        }
        bfs();
        for (int k = 0; k < max_level; ++k) {
            int cnt=0;
            for (int r=0;r<level_map[k].size();r++){
                int node=level_map[k][r];
                if(node_child[node].size()==0)
                    cnt++;
            }
            printf("%d ",cnt);
        }
        int count=0;
        for (int r=0;r<level_map[max_level].size();r++){
            int node=level_map[max_level][r];
            if(node_child[node].size()==0)
                count++;
        }
        printf("%d",count);
    }
    return 0;
}