【题目来源】
洛谷：P5908 猫猫和企鹅 - 洛谷
【题目描述】
王国里有 \(n\) 个居住区，它们之间有 \(n-1\) 条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 \(1\)。
除 \(1\) 号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从 \(1\) 号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它不大于 \(d\) 的小企鹅们。
猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。
【输入】
第一行两个整数 \(n, d\)，意义如题所述。
第二行开始，共 \(n - 1\) 行，每行两个整数 \(u, v\)，表示居民区 \(u\) 和 \(v\) 之间存在道路。
【输出】
一行一个整数，表示猫猫可以拜访多少只小企鹅。
【输入样例】
5 1
1 2
1 3
2 4
3 5
【输出样例】
2
【算法标签】
《洛谷 P5908 猫猫和企鹅》 搜索 广度优先搜索BFS #树的遍历#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, d; // n: 节点数, d: 深度限制
int u, v, ans; // u,v: 边的端点, ans: 结果计数器
vector<int> ve[100005]; // 邻接表存储树// 深度优先搜索
// x: 当前节点
// y: 父节点（避免重复访问）
// z: 当前深度
void dfs(int x, int y, int z)
{if (z >= d) // 如果深度达到限制d，停止搜索return;// 遍历当前节点的所有邻居for (int i = 0; i < ve[x].size(); i++){int tmp_v = ve[x][i]; // 邻居节点if (tmp_v == y) // 如果是父节点，跳过continue;ans++; // 统计可达节点dfs(tmp_v, x, z + 1); // 递归搜索下一层}
}int main()
{cin >> n >> d; // 读入节点数和深度限制// 读入树的边，构建邻接表for (int i = 1; i < n; i++){cin >> u >> v;ve[u].push_back(v); // 无向图，双向添加ve[v].push_back(u);}// 从节点1开始深度优先搜索dfs(1, 0, 0);cout << ans << endl; // 输出结果return 0;
}
【运行结果】
5 1
1 2
1 3
2 4
3 5
2