时间限制: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 //简单的链式前向星建图什么的
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<cstdlib>
6 using namespace std ;
7 const int maxn = 100005 ;
8 struct edge
9 {
10 int to; //目的地
11 int next; //下一个指针的坐标
12 };
13 edge str[2*maxn];
14 int head[maxn]; //头指针
15 int ans[maxn];
16 bool res[maxn];
17 void dfs(int father)
18 {
19 for(int i=head[father] ; i!=-1 ; i=str[i].next )
20 {
21 if(0==res[str[i].to])
22 {
23 ans[str[i].to]=father; //记录前一个点
24 res[str[i].to]=true;
25 dfs(str[i].to);
26 }
27 }
28 }
29 int main()
30 {
31 int m,n,s,a,b,i;
32 scanf("%d",&m);
33 while(m--)
34 {
35 scanf("%d%d",&n,&s);
36 //建立无向图
37 memset(head , -1 , sizeof(head));
38 memset(ans,-1,sizeof(ans)); //设置一个答案数组
39 memset(res,false,sizeof(res));
40 for(i=1;i<=(n-1);i++)
41 {
42 scanf("%d%d",&a,&b);
43 str[i].to=b;
44 str[i+n-1].to=a;
45 str[i].next=head[a];
46 str[i+n-1].next=head[b];
47 head[a]=i;
48 head[b]=i+n-1;
49 }
50 res[s]=true;
51 dfs(s); //从s点出发
52 for(i=1;i<=n;i++)
53 printf("%d\n",ans[i]);
54 }
55 return 0;
56 }