10503第4題血緣關係

題目來源APCS

題目網址

參考資料

解題策略(一)

使用DFS走訪兩次，第一次從任何一點出發，使用DFS走到最長路徑的另一個端點(如果有多個，任何一個都可以)，再從剛剛選定的端點出發，使用DFS找尋最長路徑的長度就是答案。

C++參考程式碼

解題策略(二)

使用深度優先搜尋(DFS)走訪樹狀結構，演算法步驟如下。

Step1)找出根(root)節點，由根(root) 節點出發進行深度優先搜尋(DFS)，也就是定義深度優先搜尋(DFS)函式，使用根(root) 節點為輸入，可以寫成DFS(root)。

Step2)深度優先搜尋(DFS)函式的程式結構，如下。

若該點沒有小孩，則回傳0，遞迴中止。

若該點只有一個小孩，則回傳並遞迴呼叫「 DFS(該小孩)+1」。

若該點有兩個以上的小孩，則計算所有小孩最大深度的前兩名相加，計算相加最大值到廣域變數md。最後回傳最大深度值，為了只有一個小孩的「DFS(該小孩)」。

Step3)遞迴呼叫DFS(root)回傳結果到變數rd，取md與rd較大值就是答案。

C++參考程式碼