题解 P5908 【猫猫和企鹅】

· · 题解

本题重点：图论，DFS深度优先搜索。

题目本质：有n个点，n-1条边（即一棵树），求深度<=d的节点有几个。

解题思路：

既然是树，又关于深度，那么肯定是要用DFS深度优先搜素的啦。

方法一：DFS遍历整棵树，求出所有点的深度即D数组，再算点的深度<=d的节点数。

方法二：在方法一的基础上增加类似暴力算法优化中的剪枝的操作，不使用D数组，而是使用计数器cnt，如发现深度>=d了，就立刻return，不需要继续做了，否则计数器++。这个做法在多数情况下可以降低时间复杂度并降低空间复杂度

此外，这一题需要使用邻接表，那么，我就在这里讲一下这个东西：

邻接表是一种存储结构，可以用于存储图，类似一个不限大小的数组。

vector< 类型 > x; : 定义邻接表 x 。

x.push_back(i); : 在邻接表 x 的后面压入 i 。

x[i] : 访问邻接表 x 的第 i 个元素。

x.size( ) : 邻接表 x 内的元素数量。

以上这些是邻接表的主要操作，另外，在存图时，需要用到 二维 的邻接表，定义方法： vector<int> x[N] 。

存图代码：

   for(int i=1;i<=n-1;i++){//树有 n-1 条边。
      int u,v;cin>>u>>v;
      es[u].push_back(v);
      es[v].push_back(u);
   }

vector+dfs 的核心代码：

   for(int i=0;i<es[x].size();i++){
      if(es[x][i]==p)continue;//p表示当前节点的父节点。
      dfs(es[x][i],x);
      //需要的操作。
   }

邻接表的主要知识就是这些啦，下面是本题AC代码：

#include<bits/stdc++.h>
#define N 100005 
using namespace std;
int n,d,cnt=0;
vector<int> es[N];
void dfs(int x,int p,int dis){
   if(dis>=d)return;
   for(int i=0;i<es[x].size();i++){
      if(es[x][i]==p)continue;
      dfs(es[x][i],x,dis+1);
      cnt++;
   }
}
int main(){
   cin>>n>>d;
   for(int i=1;i<=n-1;i++){
      int u,v;cin>>u>>v;
      es[u].push_back(v);
      es[v].push_back(u);
   } 
   dfs(1,0,0);
   cout<<cnt;
   return 0;
}