1004 Counting Leaves (30 分)

一、题目大意

题目传送门：PAT-A-1004
求树每层叶节点（0个子节点）的数量

二、解题思路

题目的这种输入简直就是为邻接表准备的???通过BFS搜索遍历这棵树。用变量cnt记录叶节点的数目，当v[h.second].size() == 0就执行cnt++。但什么时候进入下一层了呢，可以用两个变量curV和lastV来标记当前节点的层和上一个遍历的节点的层(之前看左程云的算法课中类似的题就是这么操作的)，每访问一个点时，当前的curV都是等于h.first，然后判断如果lastV != curV，则说明进入了树的下一层了，那要将cnt存入到准备打印的结果集里，并且将cnt置为0。在每一个点访问完后，此时应该执行lastV = curV，为的是让下一个点被访问的时候，有正确的lastV，在进入while循环之前，可以将lastV初始化为-1，表示根节点上一层为-1层。

三、AC代码

#include <bits/stdc++.h>
using namespace std;
template <typename T = int>
T read(){
    T x;
    cin >> x;
    return x;
}
typedef pair<int, int> pr;
int main(){
//    freopen("input.txt", "r", stdin);
    int n = read(), m = read();
    if(n == 0){
        cout << 0 << endl;
        return 0;
    }
    vector<vector<int>>v(n+1);
    vector<int>vis(n+1);
    for(int i = 0; i < m; i++){
        int id = read(), k = read();
        for(int j = 0; j < k; j++){
            v[id].push_back(read());// 邻接表存树
        }
    }
    priority_queue<pr, vector<pr>, greater<pr>>Q;
    Q.push({0, 1});
    vector<int>result;
    int cnt = 0; // 当前行叶节点的数目
    int lastV = -1, curV = 0; // 上一个点的层级，当前点的层级
    while(Q.size()){
        pr h = Q.top();
        Q.pop();
        curV = h.first;
        if(lastV != curV){// 换了一层
            result.push_back(cnt);
//            cerr << h.first << ' ' << h.second << endl;
            cnt = 0;// 叶节点重新计数
        }
        if(v[h.second].size() == 0){// 当前节点是叶节点
            cnt++;
        }
        lastV = curV;
        for(auto i: v[h.second]){
            if(vis[i] == 0){
                vis[i] = 1;
                Q.push({h.first+1, i});// 进队
            }
        }
    }
    result.push_back(cnt);// 最后一个点所在行叶节点数也记录进去
    for(int i = 1; i < result.size(); i++){// 不能输出result[0]，这是-1层的叶节点数，所以i从1开始，跳过i=0的时候。
        if(i!=1){
            cout << ' ' << result[i];
        }else{
            cout << result[i];
        }
    }
    cout << endl;
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/97092021