#LAISIR40. 拜訪所有親戚

拜訪所有親戚

🧭 題目名稱:拜訪所有親戚

📝 題目描述:

你即將參加一場家族巡禮活動,需要拜訪所有親戚。家族中的每對親戚透過血緣關係形成一棵樹。你從某個人出發,想要依照「深度優先搜尋(DFS)」的順序拜訪所有人。

請輸出你實際拜訪親戚的順序,假設每次都優先拜訪編號較小的成員。


📥 輸入格式:

第一行一個整數 n(2 ≤ n ≤ 10⁴):家族成員數 接下來 n−1 行,每行兩個整數 u v,表示成員 uv 有親戚關係 最後一行一個整數 r(1 ≤ r ≤ n),代表從編號為 r 的成員開始拜訪


📤 輸出格式:

輸出一行 n 個整數,為 DFS 拜訪的順序,每個成員編號以空格分隔


📘 輸入範例:

5
1 2
1 3
3 4
3 5
1

📗 輸出範例:

1 2 3 4 5

(說明:DFS 從 1 開始,先拜訪 2,再回來拜訪 3、4、5)


✅ 示意圖(可手繪或畫出)

        1
       / \
      2   3
         / \
        4   5

DFS 拜訪順序:

1 → 2 → 3 → 4 → 5