zzuli生化危机（dfs）-布布扣-bubuko.com

生化危机

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 73 Solved: 21
Submit Status Web Board

Description

X博士想造福人类, 研发一种可以再生肢体的药物, 可是很不幸......研究失败了, 他在蜥蜴身上实验的时候, 蜥蜴发生了变异, 更糟糕的是, 蜥蜴逃出了生化实验室.

恐怖的事情发生了, 疫情以X博士所在的城市为中心向四周扩散开, 最终, 整个地球上的城市都被感染了.假设整个地球一共有N个城市, 这N个城市是连通的, 有N-1条通道把他们连接起来.病毒会以一座城市为中心,在一天的时间内, 会把和他相连的周围的所有城市感染. 那么, 多少天的时间, 整个地球的城市都感染呢?

Input

第一行输入一个T(T <= 50), 表示一共有T组测试数据. 每组数据第一行两个数n, k. n表示有n(2 <= n <= 10000)个城市, 代表城市1-n, k是X博士所在的城市. 接下来n-1行, 每行有两个数u, v, 表示城市u和v之间有一条通道.

Output

每组数据第一行输出第一个数 x , 表示整个地球感染需要x天. 接下来 x 个数, 第i个数表示第i天感染了城市的数量. (注意，每组数据第二行每个数据后边都有一个空格）.

Sample Input

2 3 1 1 2 2 3 3 2 1 2 2 3

Sample Output

3 1 1 1 2 1 2

题解：树的深度，以及每层的结点数；注意初始化；

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<vector>
 7 using namespace std;
 8 #define mem(x,y) memset(x,y,sizeof(x))
 9 typedef long long LL;
10 const int MAXN=10010;
11 vector<int>vec[MAXN];
12 int dep[MAXN],vis[MAXN],num[MAXN];
13 int ans;
14 void dfs(int u){
15     vis[u]=1;num[1]=1;
16     for(int i=0;i<vec[u].size();i++){
17         int v=vec[u][i];
18         if(!vis[v]){
19             vis[v]=1;
20             dep[v]=dep[u]+1;num[dep[v]]++;
21             ans=max(ans,dep[v]);
22             dfs(v);
23         }
24     }
25 }
26 int main(){
27     int T,a,b,n,k;
28     scanf("%d",&T);
29     while(T--){
30         scanf("%d%d",&n,&k);
31         for(int i=1;i<=n;i++)vec[i].clear();
32         for(int i=1;i<n;i++){
33             scanf("%d%d",&a,&b);
34         vec[a].push_back(b);
35         vec[b].push_back(a);
36         }
37         mem(vis,0);mem(num,0);ans=0;
38         for(int i=1;i<=n;i++)dep[i]=1;
39         dfs(k);
40         printf("%d\n",ans);
41         for(int i=1;i<=ans;i++){
42             //if(i!=1)printf(" ");
43             printf("%d ",num[i]);
44         }puts("");
45     }
46     return 0;
47 }

zzuli生化危机（dfs）

原文：http://www.cnblogs.com/handsomecui/p/4986938.html