吝啬的国度
时间限制：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
无环无向图，寻找某点到所有其它点的最短路径。一开始用的dijkstra，超时，后来改成深度搜索就好了，广度搜索也能做。由于N过大，所以用邻连矩阵表示图的连接情况，太耗空间，所以这里用邻接表。
#include
<stdio.h>02.#include
<vector>03.#include
<string.h>04.using namespace std;05. 06.#define
MAXN 10000507. 08.int path[MAXN],vis[MAXN];09. 10.vector<
vector<int>
> v;11. 12.void dfs(int k)13.{14.vis[k]=1;15.vector<int>::iterator
it=v[k].begin();16.for(;it!=v[k].end();it++)17.{18.if(vis[*it]==0)19.{20.path[*it]=k;21.dfs(*it);22.}23.}24.}25. 26.int main()27.{28.int M,N,S,a,b;29.scanf("%d",&M);30.while(M--)31.{32.scanf("%d%d",&N,&S);33.v.resize(N+1);34.for(int i=0;i<N-1;i++)35.{36.scanf("%d%d",&a,&b);37.v[a].push_back(b);38.v[b].push_back(a);39.}40.memset(vis,0,sizeof(vis));41.dfs(S);42.path[S]=-1;43.for(int i=1;i<N;i++)44.printf("%d
",path[i]);45.printf("%d\n",path[N]);46.v.clear();47.}48.return 0;49.}
上面的是正常思路，耗时还是挺多的，该算法耗时260ms，当时平台排第一的算法耗时只有36ms。内存也用得少了。
下面的算法思路基本是这样的（我的理解）：map[a]=b,可以理解为b是a的父亲。
当输入a,b时，如果b没有父亲，就让a作为b的父亲;
如果b已经有父亲了，那就调整a，让a的父亲，a的父亲的父亲…关系颠倒，即让map[a]=a1,map[a1]=map[a2]…变成map[a2]=a1,map[a1]=a,这样a是其子孙的父亲，然后让b成为a的父亲
上面这两步，主要作用就是让所有节点间的关系是成单向的。这样，最后只要对S节点进行上述的颠倒调整就可以了。
#include
<stdio.h> 02.#include
<memory.h> 03.int map[100005]; 04. 05.void Adjust(int currentCity) 06.{ 07.int priorCity
= map[currentCity]; 08.if (priorCity
!= 0) 09.{ 10.Adjust(priorCity); 11.map[priorCity]
= currentCity; 12.} 13.} 14. 15. 16.int main() 17.{ 18.int i,
n, m, s, A, B; 19.scanf("%d",
&n); 20.while (n--) 21.{ 22. 23. 24.scanf("%d%d",
&m, &s); 25. 26. 27.memset(map,
0, sizeof(map)); 28. 29. 30.//
for(i=0;i<20;i++)31.//
printf("%d ",map[i]);32. 33. 34.for (i
= 1; i < m; i++) 35.{ 36.scanf("%d%d",
&A, &B); 37. 38. 39.if (map[B]
== 0) 40.map[B]
= A; 41.else 42.{ 43.Adjust(A); 44.map[A]
= B; 45.}46.//
printf("**************%d \n",map[A]);47.}48. 49. 50.Adjust(s); 51.map[s]
= - 1; 52. 53. 54. 55. 56.for (i
= 1; i <=m; i++) 57.printf("%d
",
map[i]); 58. 59.printf("\n"); 60.} 61.return 0; 62.}