#LAISIR40. 拜訪所有親戚
拜訪所有親戚
🧭 題目名稱:拜訪所有親戚
📝 題目描述:
你即將參加一場家族巡禮活動,需要拜訪所有親戚。家族中的每對親戚透過血緣關係形成一棵樹。你從某個人出發,想要依照「深度優先搜尋(DFS)」的順序拜訪所有人。
請輸出你實際拜訪親戚的順序,假設每次都優先拜訪編號較小的成員。
📥 輸入格式:
第一行一個整數 n
(2 ≤ n ≤ 10⁴):家族成員數
接下來 n−1 行,每行兩個整數 u v
,表示成員 u
與 v
有親戚關係
最後一行一個整數 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
Related
In following homework: