第五章 树 1 AcWing 1476. 数叶子结点

第五章 树 1 AcWing 1476. 数叶子结点

原题链接

AcWing 1476. 数叶子结点

算法标签

树的遍历 BFS DFS

思路

树的遍历往往即可以使用BFS, 也可以使用DFS, 由于DFS需要维护队列， 相比于BFS较为麻烦，因此通常使用BFS。
对于树与图的存储，常常使用邻接表存储。
使用邻接表存储示意图：

遍历至叶子结点将对应深度加1，同时更新最大深度以便于输出。
采用邻接表存储图，h[u]=-1表示无孩子即为叶节点，否则从上到下遍历孩子节点，传入的深度 depth+1 ， 详细思路见代码。

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define x first
#define y second
#define ump unordered_map
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pair PII;
const int N = 105;
//int t, n, m, cnt, ans; 
// 对于树形数据结构，邻接表存储对象
// h[i]树中每个节点 需要事先初始化为头节点
// e[i]表示节点i对应的值
// ne[i]表示节点i相邻下一个节点位置
// idx存储当前所用到的点

int h[N], e[N], ne[N], idx;
int cnt[N], mx;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void add(int a, int b){
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
void dfs(int u, int d){
    // 遍历到叶子节点
    if(h[u]==-1){
        // 对应深度处的数量加1
        cnt[d]++;
        // 更新最大深度以便于最后的输出
        mx=max(mx, d);
        return;
    }
    // 非叶子节点 遍历所有的孩子节点 传入的深度 d+1
    for(int i=h[u]; ~i; i=ne[i]){
        dfs(e[i], d+1);
    }
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=rd(), m=rd();
	memset(h, -1, sizeof h);
	while(m--){
	    int id=rd(), k=rd();
	    while(k--){
	        int son=rd();
	        add(id, son);
	    }
	}
	dfs(1, 0);
	printf("%lld", cnt[0]);
	rep(i, 1, mx+1){
	    printf("% lld", cnt[i]);
	}
	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
61
62
63
64
65
66
67
68
69
70
71

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈