Pet
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1088 Accepted Submission(s): 536
Problem Description
One day, Lin Ji wake up in the morning and found that his pethamster escaped. He searched in the room but didn’t find the hamster. He tried to use some cheese to trap the hamster. He put the cheese trap in his room and waited for
three days. Nothing but cockroaches was caught. He got the map of the school and foundthat there is no cyclic path and every location in the school can be reached from his room. The trap’s manual mention that the pet will always come back if it still in somewhere
nearer than distance D. Your task is to help Lin Ji to find out how many possible locations the hamster may found given the map of the school. Assume that the hamster is still hiding in somewhere in the school and distance between each adjacent locations is
always one distance unit.
Input
The input contains multiple test cases. Thefirst line is a positive integer T (0<T<=10), the number of test cases. For each test cases, the first line has two positive integer N (0<N<=100000) and D(0<D<N), separated by a single space.
N is the number of locations in the school and D is the affective distance of the trap. The following N-1lines descripts the map, each has two integer x and y(0<=x,y<N), separated by a single space, meaning that x and y is adjacent in the map. Lin Ji’s room
is always at location 0.
Output
For each test case, outputin a single line the number of possible locations in the school the hamster may be found.
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
这题我没读懂，英语底子太烂没办法。同学读的。
拿到这题第一个问题就把我难住了。、平时学的数据结构运用的很少所以就蛋痛了。
拿到这题最开始我想了想能不能用并查集来解答，结果是必然的不能。因为并查集在实现的时候只关注了父节点。分类。
当我网上找解答的时候，我的目的很明确，就是看看人家怎么建的树。学习一下其他的自己来实现。
一看vector就行了。我一看“醍醐灌顶”，唉。。。
接着来吧，搜索的话我的想法就是广度优先遍历。后来我发现网上大部分都是用深搜来解答的。、
广度嘛这样可以很好的找到大于d的节点了
这样一层一层的遍历 当层数大于d 以后的所有没遍历的点就是要求的了 。
其中还有很多细节问题 就是比如说建树的时候因为100000个点太大 所以要做成全局变量。不然的话因为太大报错。
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[100001];
bool b[100001];//标记是否用过
int main()
{
int cases ;
scanf("%d",&cases);
while(cases--)
{
memset(b,false,sizeof(b));
int len[100001];
int n,d,x,y;
scanf("%d%d",&n,&d);
for(int i=0;i<=n;i++)//清空上组的v[];
{
v[i].clear();
}
for(int i=1;i<n;i++)//建树
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
len[0]=0;
queue<int> q;//这是普通的广度优先搜索算法
q.push(0);
b[0]=true;
int ans=0;
while(!q.empty())
{
int t = q.front();
q.pop();
for(int i=0;i<v[t].size();i++)
{
int x=v[t][i];
if(b[x]==false)
{
len[x]=len[t]+1;
q.push(x);
b[x]=true;
if(len[x]>d)
ans++;//统计个数
}
}
}
cout<<ans<<endl;
}
}
就这样 代码很简单
感谢自己继续坚持！
深度优先搜索,布布扣,bubuko.com
深度优先搜索
原文：http://blog.csdn.net/u010123208/article/details/23666713
