题解：洛谷 P5908 猫猫和企鹅

张开发
• 2026/4/17 23:47:21 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

题解：洛谷 P5908 猫猫和企鹅
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P5908 猫猫和企鹅 - 洛谷【题目描述】王国里有n nn个居住区它们之间有n − 1 n-1n−1条道路相连并且保证从每个居住区出发都可以到达任何一个居住区并且每条道路的长度都为1 11。除1 11号居住区外每个居住区住着一个小企鹅有一天一只猫猫从1 11号居住区出发想要去拜访一些小企鹅。可是猫猫非常的懒它只愿意去距离它不大于d dd的小企鹅们。猫猫非常的懒因此希望你告诉他他可以拜访多少只小企鹅。【输入】第一行两个整数n , d n, dn,d意义如题所述。第二行开始共n − 1 n - 1n−1行每行两个整数u , v u, vu,v表示居民区u uu和v vv之间存在道路。【输出】一行一个整数表示猫猫可以拜访多少只小企鹅。【输入样例】5 1 1 2 1 3 2 4 3 5【输出样例】2【算法标签】#普及-# #DFS-树#【代码详解】#includebits/stdc.husingnamespacestd;intn,d;// n: 节点数, d: 深度限制intu,v,ans;// u,v: 边的端点, ans: 结果计数器vectorintve[100005];// 邻接表存储树// 深度优先搜索// x: 当前节点// y: 父节点避免重复访问// z: 当前深度voiddfs(intx,inty,intz){if(zd)// 如果深度达到限制d停止搜索return;// 遍历当前节点的所有邻居for(inti0;ive[x].size();i){inttmp_vve[x][i];// 邻居节点if(tmp_vy)// 如果是父节点跳过continue;ans;// 统计可达节点dfs(tmp_v,x,z1);// 递归搜索下一层}}intmain(){cinnd;// 读入节点数和深度限制// 读入树的边构建邻接表for(inti1;in;i){cinuv;ve[u].push_back(v);// 无向图双向添加ve[v].push_back(u);}// 从节点1开始深度优先搜索dfs(1,0,0);coutansendl;// 输出结果return0;}【运行结果】5 1 1 2 1 3 2 4 3 5 2

更多文章