1. 问题描述：
在一个吝啬的国度里有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
2. 思路分析：
① 简单分析一下题目可以知道这些城市和道路之间构成了极小联通子图，也就是生成树，从任意一个城市出发都可以通过另外一个城市，而出发的城市S就相当于这棵树的树根，一种较易想到的解法就是就是从这个根出发，对整棵树进行深度优先搜索遍历，过程中记录下前一个城市的编号
② 首先对于题目中的一个关键点我们是要特别要考虑的，那就是假如出发城市不同那么我们所得到的结果也是不一样的，上面的例子是以1这个城市作为出发点的，在测试数据的时候也有可能是以2作为出发点，那么这个时候就要以2这个节点作为整棵树的树根，把上面的树拉上去，然后对树进行深度优先遍历，所以我们在编程的时候需要进行双向的标记
③ 怎么样进行双向的标记呢？首先我们需要做的是对于当前的节点，我们怎么样处理它与子节点之间的关系，例如上面的1这个节点与8,9,2这三个节点怎么样把他们联系在一起，不难想到的是使用链表来进行链接，把1这个节点下的所有子节点形成一个单链表这样就把他们联系在一起了
链接的方式使用的是节点的next指针，所以要创建一个内部类来封装这个节点，需要考虑封装到这个节点的属性有哪些，首先是当前节点的值，可以使用当前下标表示当前的根节点的值（代表的也是出发城市），第二个是next指针，指向下一个节点，第三个是我们需要记录当前节点的前一个节点，使用int类型来表示
因为考虑到由于出发城市的不同那么作为树的根的节点就不同，所以需要进行双向标记，这个时候需要创建一个Node类型的数组（对象数组），Node里面的元素是一个Node节点，当前的下标表示的是当前节点，当我们输入两个城市的连接的时候那么我们新建两个节点把这两个节点加入到类数组对应的位置上，例如输入1 9的时候先判断当前对象数组的下标对应的节点是否为空，为空那么新建一个节点作为当前这个位置上链表的头结点，不为空那么把节点加入到当前对象数组对应下标的链表的末尾
所以通过上面的双向标记之后每一个对象数组的元素都是一个链表，而且把当前节点与其他节点的联系都建立起来了，例如尚明的以1作为出发城市那么，1---8---9---2联系起来，双向标记8---1,9---1,2---1联系起来，这样在接下来的对于以出发城市为起点做深度优先遍历的话那么就可以找到相互联系的节点了
for(int j = 0; j < totalCity - 1; j++){
int start = sc.nextInt();
int end = sc.nextInt();
//新建两个新的节点是非常关键的这样指针的指向才不会发生错误
Node A = new Node(start);
Node B = new Node(end);
if(nodes[start] == null){
nodes[start] = new Node(start);
}
if(nodes[end] == null){
nodes[end] = new Node(end);
}
Node p = nodes[start];
while(p.next != null){
p = p.next;
}
p.next = B;
p = nodes[end];
while(p.next != null){
p = p.next;
}
p.next = A;
}
④ 我们可以在深搜之前测试一下创建的链表到底对不对。可以对创建的对象数组的节点进行输出（在循环输入所有数据之后输出），但是要重写Node节点的toString方法，输出结果：
for(int k = 1; k < totalCity; k++){
System.out.println(nodes[k]);
}
可以在控制台看到输出结果：
可以看到以出发城市不同，节点相互之间的联系就建立起来了，凡是与当前的节点有联系的节点都使用next指针联系起来，需要注意的是
1节点与9这个节点通过next指针指向的1节点是不一样的节点，而且我们只是需要其中的下标而已这样在深度优先搜索的时候那么就可以通过对象数组的下标对应的节点找到其他与当前元素的节点，而且必须在循环中每一次都要创建新的两个节点这样指针的指向才不指错
⑤ 以出发城市作为起点深度优先搜索整个图，可以根据上面整棵树的图来写出深搜的代码，我们通过的是下标来访问出发城市，以出发城市搜索链表，因为需要记录当前城市的上一个城市，所以需要传入的是两个参数，一个是当前城市，另外一个是当前城市的上一个城市，需要使用一个循环来进行递归，因为链表中的元素不止一个，而深搜是一条路走到黑的，所以需要在循环中递归，其中需要注意的是不能够使用当前节点的next的priorCity作为是否进行下一次的递归的判断，例如1这个节点与9这个节点通过next联系到的1这个节点是不一样的，因为9递归到1这个节点，9这个节点的next指向的1的这个节点不是之前的nodes[1]这个节点所以它的priorCity是为空的，但是nodes[1]的priorCity是不为空的，假如像上面这样Node currentCity = nodes[startCity].next
if(currentCity.priorCuty == 0)会造成重复1-9之间递归下去导致堆栈溢出
基于上面的考虑，于是我们可以使用Set这个数据结构来存储已经访问过的节点这样就可以了，还可以像上面说的要使用nodes的下标对应的节点对应的priorCity来进行判断，而不是当前节点的下一个节点的priorCity来进行判断是否进行递归，像下面这样写是正确的‘
private static void dfs(int startCity, int priorCity, Node nodes[], Set<Integer> set) {
set.add(startCity);
Node currentCity = nodes[startCity].next;
nodes[startCity].priorCity = priorCity;
while(currentCity != null){
if(nodes[currentCity.value].priorCity == 0){
dfs(currentCity.value, startCity, nodes, set);
}
currentCity = currentCity.next;
}
}
3. 代码如下：
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node[] nodes = null;
for(int i = 0; i < n; i++){
int totalCity = sc.nextInt();
int startCity = sc.nextInt();
nodes = new Node[totalCity + 1];
Set<Integer> set = new HashSet<Integer>();
for(int j = 0; j < totalCity - 1; j++){
int start = sc.nextInt();
int end = sc.nextInt();
Node A = new Node(start);
Node B = new Node(end);
if(nodes[start] == null){
nodes[start] = new Node(start);
}
if(nodes[end] == null){
nodes[end] = new Node(end);
}
Node p = nodes[start];
while(p.next != null){
p = p.next;
}
p.next = B;
p = nodes[end];
while(p.next != null){
p = p.next;
}
p.next = A;
}
dfs(startCity, -1, nodes, set);
for(int k = 1; k <= totalCity; k++){
System.out.print(nodes[k].priorCity + " ");
}
}
sc.close();
}
private static void dfs(int startCity, int priorCity, Node nodes[], Set<Integer> set) {
set.add(startCity);
Node currentCity = nodes[startCity].next;
nodes[startCity].priorCity = priorCity;
while(currentCity != null){
if(!set.contains(currentCity.value)){
dfs(currentCity.value, startCity, nodes, set);
}
currentCity = currentCity.next;
}
}
public static class Node{
public int value;
public Node next;
public int priorCity;
@Override
public String toString() {
return "Node [value=" + value + ", next=" + next + ", priorCity=" + priorCity + "]";
}
public Node(int value) {
super();
this.value = value;
}
}
}
4. 总结一下：这道题目我们需要学会单链表插入节点的操作，怎么样将相关的节点全部联系起来，方法是使用一个类来封装节点，在节点中使用next指针连建立链表，而且需要创建一个对象数组来表示当前的节点，创建两个新的节点把节点加入到对应的对象数组的下标中