题目链接：点击这里

题意：家族层次结构通常由系谱树表示。你的工作是清点那些没有孩子的家庭成员。

1.BFS

思路：使用邻接表来存储树。利用BFS对树进行层次遍历，由于题目中要求每一层的叶子结点的个数，为了方便，我们可以使用两个队列，初始根节点放入 $q_1$，$q_2$ 为空；然后将 $q_1$ 中的节点能扩展出来的所有节点放入 $q_2$，$q_1$ 为空； 接着将 $q_2$ 中的节点能扩展出来的所有节点放入 $q_1$，$q_2$ 为空……如此循环，直到两个队列同时为空结束循环。

AC代码：

#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; const int N = 110; vector<int> g[N]; int ans[N], depth; void bfs() { queue<int> q1, q2; q1.push(1); while(q1.size() || q2.size()) { depth++; if(q1.size()) { while(q1.size()) { int t = q1.front(); q1.pop(); if(g[t].size() == 0) ans[depth]++; else for(int i = 0; i < g[t].size(); i++) q2.push(g[t][i]); } } else { while(q2.size()) { int t = q2.front(); q2.pop(); if(g[t].size() == 0) ans[depth]++; else for(int i = 0; i < g[t].size(); i++) q1.push(g[t][i]); } } } } int main() { int n, m; scanf("%d%d", &n, &m); while(m--) { int a, k, b; scanf("%d%d", &a, &k); while(k--) { scanf("%d", &b); g[a].push_back(b); } } bfs(); for(int i = 1; i <= depth; i++) printf("%d%c", ans[i], i == depth ? '\n' : ' '); return 0; }

2.DFS

思路：用数组模拟邻接表存储树。对树进行深度优先遍历，深搜的过程中还需要记录树的深度，每次到达递归边界，就说明到达了一个叶节点，那么当前深度的叶子节点数加 $1$ 即可。

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 110; int h[N], e[N], ne[N], idx; int ans[N], max_depth; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u, int depth) { if(h[u] == -1) // u是叶子节点 { ans[depth]++; max_depth = max(max_depth, depth); return; } for(int i = h[u]; ~i; i = ne[i]) dfs(e[i], depth + 1); } int main() { int n, m; scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while(m--) { int a, k, b; scanf("%d%d", &a, &k); while(k--) { scanf("%d", &b); add(a, b); } } dfs(1, 1); for(int i = 1; i <= max_depth; i++) printf("%d%c", ans[i], i == max_depth ? '\n' : ' '); return 0; }

微信公众号《算法竞赛求职》，致力于详细讲解竞赛和求职所涉及到的算法原理和模板。欢迎关注，一起交流进步！