#45900: 解題思路


henry.rem.rem@gmail.com (*ฅ́˘ฅ̀*)

學校 : 臺北市立松山高級中學
編號 : 278368
來源 : [1.161.41.35]
最後登入時間 :
2025-05-05 21:10:22
b967. 4. 血緣關係 -- 2016年3月apcs | From: [36.224.155.174] | 發表日期 : 2025-04-26 20:21

解題思路:

題目要求找出兩個血緣關係最遠的成員之距離。

首先可以發現,距離的其中一端必定包含位於最深處的節點(才能讓關係最遙遠),

接著只需要找出位於另一端的節點,即可求得最遠的血緣距離。

實作策略:

為了找出位於最深處的節點之一,我們需要先知道誰是根節點。而根節點只要能夠成功建立樹結構,就能輕易得出。

其次需要找到位於最深處的節點。我們可以利用 BFS ,從根節點開始逐層搜尋,並維護最深的節點。

其實這部分用 DFS 也可以找到,只是在實作上,會多了需要判斷當前節點高度的步驟,不像 BFS 會自然維護節點距離,

較為繁瑣且容易出錯,故推薦使用 BFS 實作。

在取得最深處的節點後,以其作為起點,進行第二次 BFS ,並計算各節點與其的距離,在找到最遠處節點後即可完成。

範例解法

 
ZeroJudge Forum