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指針連建立連結清單，而且需要建立一個對象數組來表示目前的節點，建立兩個新的節點把節點加入到對應的對象數組的下标中