zzulioj 1787: 生化危机 （vector+dfs） 好题

1787: 生化危机

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 70   Solved: 20

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   //是个好题，用邻接表写，一直不对....（技术不行）。经好友提醒指导，最终过了。

#include<stdio.h>   
#include<string.h>   
#include<vector>   
#include<string>   
#include<iostream>   
using namespace std;  
int dis[100100];  
int xx[10010];
vector<int>v[100100];  
void dfs(int x)  
{  
    int i;  
    for(i=0;i<v[x].size();i++)  
    {  
    if(dis[v[x][i]]==0)
    {
        dis[v[x][i]]=dis[x]+1;
        xx[dis[v[x][i]]]++;
        dfs(v[x][i]);
        }
    }  
}  
int main()  
{     
    int t;
    scanf("%d",&t);
    while(t--)  
    {  
        int n,d,i;               
        scanf("%d%d",&n,&d);  
        for(i=1;i<=n;i++)  
            v[i].clear();  
        for(i=1;i<n;i++)  
        {
            int a,b;
            scanf("%d%d",&a,&b);
            v[a].push_back(b); 
v[b].push_back(a); 
        }  
        memset(dis,0,sizeof(dis)); 
memset(xx,0,sizeof(xx)); 
dis[d]=1;
        dfs(d);
        int cnt=1;
        for(i=1;i<=n;i++)
        if(xx[i])
        cnt++;
        printf("%d\n",cnt);
        printf("1 ");
        for(i=1;i<=n;i++)
        {
        if(xx[i])
        printf("%d ",xx[i]);//这块最后一个输出多个空格 
        }
        printf("\n");        
    }  
    return 0;
}