1787: 生化危机
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 97 Solved: 29
SubmitStatusWeb 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
3 1
1 2
2 3
3 2
1 2
2 3
Sample Output
3
1 1 1
2
1 2
dis数组记录每一个节点的被污染日期,xx数组记录每一天有多少个城市被污染,vector建图建的无向图,遍历的时候遍历节点下边每一个未污染的点,dis=0就表示该城市未被污染
1 1 1
2
1 2
dis数组记录每一个节点的被污染日期,xx数组记录每一天有多少个城市被污染,vector建图建的无向图,遍历的时候遍历节点下边每一个未污染的点,dis=0就表示该城市未被污染
#include<stdio.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; vector<int>g[10010]; int xx[10010],dis[10010]; void dfs(int x) { for(int i=0;i<g[x].size();i++) { if(dis[g[x][i]]==0) { dis[g[x][i]]=dis[x]+1;//记录一个城市被污染的日期 xx[dis[g[x][i]]]++;//记录同一天有多少城市被污染 dfs(g[x][i]); } } } int main() { int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) g[i].clear(); int a,b; for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); g[a].push_back(b);//无向图 g[b].push_back(a); } memset(dis,0,sizeof(dis)); memset(xx,0,sizeof(xx)); dis[k]=1; //从源头城市开始dfs,初始化 dfs(k); int cnt=1; for(int i=1;i<=n;i++) if(xx[i]) cnt++;//遍历每一个时间,看需要多久完全被污染 printf("%d ",cnt); printf("1 "); for(int i=1;i<=n;i++) { if(xx[i]) printf("%d ",xx[i]); } printf(" "); } return 0; }