hdu 4707 仓鼠 记录深度 (BFS)

题意：linji的仓鼠丢了，他要找回仓鼠，他在房间0放了一块奶酪，按照抓鼠手册所说，这块奶酪可以吸引距离它D的仓鼠，但是仓鼠还是没有出现，现在给出一张关系图，表示各个房间的关系，相邻房间距离为1，而且图中没有回路，每个房间都是联通的，求仓鼠可能出现的房间的数量。

Sample Input
1
10 2
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
6 9

Sample Output
2

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <vector>

 #include <queue>

 using namespace std;

 const int MAXN = ;

 vector<int>vec[MAXN];

 int dep[MAXN];

 int pre[MAXN];

 void bfs(int s)

 {

     memset(dep,-,sizeof(dep));

     dep[s] = ;

     queue<int>q;

     q.push(s);

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         int sz = vec[u].size();

         for(int i = ;i < sz;i++)

         {

             int v = vec[u][i];

             if(dep[v] != -)continue;

             dep[v] = dep[u] + ;

             pre[v] = u;

             q.push(v);

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin) ;

     int T;

     int n;

     int D;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&D);

         int u,v;

         for(int i = ;i < n;i++)

             vec[i].clear();

         for(int i = ;i < n;i++)

         {

             scanf("%d%d",&u,&v);

             vec[u].push_back(v);

             vec[v].push_back(u);

         }

         bfs();

         int ans = ;

         for(int i = ;i < n;i++)

             if(dep[i] > D)

                 ans++;

         cout<<ans<<endl;

     }

     return ;

 }