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 //简单的链式前向星建图什么的
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 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-05-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
