旅行家Sam要游玩N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。
Sam准备从第S号城市出发，他想知道如果自己要去参观第K号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。
第一行输入一个整数T表示测试数据共有T (1 ≤ T ≤ 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
4 1
1 2
1 3
2 4
-1 1 1 2
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 int n;
5 int m,s;
6 vector<vector<int> > vec;//用邻接表来存储图
7 vector<int> f;//来存储各个城市的前一个城市
8 void dfs(int s){
9 int len=vec[s].size();//len存储的是s城市与几个城市之间有路
10 for(int i=0;i<len;i++){
11 if(f[vec[s][i]])//如果去过这个城市，那就跳过，防止走重复的路
12 continue;
13 f[vec[s][i]]=s;//到达vec[s][i]城市必须经过的前一个城市是s
14 dfs(vec[s][i]); //继续从vec[s][i]城市开始搜索
15 }
16 }
17 int main(){
18 scanf("%d",&n);
19 while(n--){
20 scanf("%d%d",&m,&s);
21 vec.resize(m+1);
22 f.assign(m+1,0);
23 for(int i=1;i<m;i++){
24 int a,b;
25 scanf("%d%d",&a,&b);
26 vec[a].push_back(b);//用邻接表来存储
27 vec[b].push_back(a);
28 }
29 f[s]=-1;
30 dfs(s);
31 for(int i=1;i<=m;i++){
32 printf("%d ",f[i]);
33 }
34 printf("\n");
35 vec.clear();
36 }
37 return 0;
38 }
这道题的思路就是搜索，从开始的城市开始搜索，
假设开始的城市是a
a城市与b城市之间有路，并紧邻着
那么去b城市必须要经过的城市就是a，
就这样依此类推
这道题有一个点就是数据太大，
要是用邻接矩阵来存储图肯定不行
所以要用邻接表来存储