a047:
1050305 第 4 題 血緣關係
內容
問題描述
小宇有一個大家族。有一天，他發現記錄整個家族成員和成員間血緣關係的家族族 譜。小宇對於最遠的血緣關係 (我們稱之為"血緣距離") 有多遠感到很好奇。
上圖為家族的關係圖。0 是 7 的孩子，1、2 和 3 是 0 的孩子，4 和 5 是 1 的孩子，6 是 3 的孩子。我們可以輕易的發現最遠的親戚關係為 4(或 5)和 6，他們的"血緣距離"是 4 (4~1，1~0，0~3，3~6)。
給予任一家族的關係圖，請找出最遠的 "血緣距離"。你可以假設只有一個人是整個家族成員的祖先，而且沒有兩個成員有同樣的小孩。
輸入說明
第一行為一個正整數 n 代表成員的個數，每人以 0~n-1 之間惟一的編號代表。接著 的 n-1 行，每行有兩個以一個空白隔開的整數 a 與 b (0 ≤ a,b ≤ n-1)，代表 b 是 a 的 孩子。
輸出說明
每筆測資輸出一行最遠"血緣距離"的答案。
範例輸入
#1
範例一 ：輸入 8 0 1 0 2 0 3 7 0 1 4 1 5 3 6 範例二 ：輸入 4 0 1 0 2 2 3
範例輸出
#1
範例一 ：正確輸出 4 範例二 ：正確輸出 3
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <10M
提示 ：
範例一說明：
如題目所附之圖，最遠路徑為 4->1 ->0 ->3 ->6 或 5->1 ->0 ->3 ->6 ，距離 為 4。
範例二說明：
最遠路徑為 1->0 ->2 ->3 ，距離為 3。
出處:
APCS 委員會004
[管理者：
zero(管理員)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||