NYOJ 20

吝啬的国度

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

 

输入

第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1）

样例输入

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

样例输出

-1 1 10 10 9 8 3 1 1 8

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6
 7 int p[100010] = {0};
 8 //vector <int > g[100010];//用这个表示二维数组的话，没法直接用clear方法，若用for循环清空怕费时间
 9 //vector <vector <int > > g(100010);
10 vector<vector<int> > g(100010,vector<int>());
11 int n,s;//注意s从1开始
12
13 void read_tree()
14 {
15      int u,v,i,j,k;
16      scanf("%d%d",&n,&s);
17      for(i=0;i<n-1;i++)
18      {
19           scanf("%d%d",&u,&v);
20           g[u].push_back(v);//与u的相邻点
21           g[v].push_back(u);
22      }
23 }
24
25 void dfs(int u,int father)//递归转化为以U为根的子树，父节点为father
26 {
27      int i,j,k;
28      int d = g[u].size();//与u的相邻点 个数
29      for(i=0;i<d;i++)
30      {
31           int v = g[u][i];//u大的第i个相邻点是v
32           if(v!=father)//不加的话会无限递归
33                dfs(v,p[v] = u);//v的父亲设为u ，归转化为以归转化为以U为根的子树为根的子树
34      }
35 }
36
37 int main()
38 {
39      int i,j,k,T;
40      scanf("%d",&T);
41      while(T--)
42      {
43           //g.clear();//用这个清空，一直re
44           for(i=0;i<100010;i++)//也可以直接memset
45                g[i].clear();
46           memset(p,0,sizeof(p));
47           read_tree();
48           p[s] = -1;
49           dfs(s,-1);
50           //printf("-1");//不能线输出-1,第一个不应定是-1
51           for(i=1;i<=n;i++)
52                printf("%d ",p[i]);
53           printf("\n");//nyoj上加\b会wa
54      }
55      return 0;
56 }
57
58
59
60