【題解】ZeroJudge b967: 第 4 題 血緣關係

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b967
【解題想法】DFS【筆記

  • 題目的樹是一個無向圖 (圖1)。
  • 不管先抓起哪個節點當成root,都還是一棵樹 (圖2、圖3)。
  • (圖3) 從「節點 0」 (當成root)開始做DFS,計算每個節點與「節點 0」的距離 (depth)。(不管從哪個節點開始,最後答案都會一樣。)
  • 選一個與(圖3)中「節點 0」距離最遠(即depth最大)的節點(一定是原樹的leaf node)當成新的root (圖4 中的「節點 4」),再做一次DFS,計算每個節點與「節點 4」的距離 (depth)。
  • depth 的最大值即為答案。
#include <iostream>
#include <vector>
using namespace std;
 
vector <int> g[100005];
int a[100005];
 
void dfs(int now, int pre){
    for (auto i:g[now]){
        if (i != pre){
            a[i] = a[now]+1;
            dfs(i, now);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while (cin >> n){
        for (int i = 0; i < n; i++){
            g[i].clear();
            a[i] = 0;
        }
        for (int i = 0; i < n-1; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(0, -1);
        int idx = 0, mx = 0;
        for (int i = 0; i < n; i++){
            if (a[i] > mx){
                mx = a[i];
                idx = i;
            }
        }
        for (int i = 0; i < n; i++){
            a[i] = 0;
        }
        dfs(idx, -1);
        for (int i = 0; i < n; i++){
            if (a[i] > mx){
                mx = a[i];
            }
        }
        cout << mx << '\n';
    }
}

Python 程式碼 (credit: Amy Chou)
【注意】DFS做法,使用Python寫代碼,最後一組測資發生 Segmentation fault (core dumped)。
【注意】換成下面做法試試看,但最後一組測資 TLE

while True:
    try:
        N = int(input())
        parent = [-1 for _ in range(N)]
        children = [list() for _ in range(N)]
        for _ in range(N-1):
            a, b = map(int, input().split())
            parent[b] = a
            children[a].append(b)

        leaf = list()
        for i in range(N):
            if (len(children[i]) == 0):
                leaf.append(i)

        for i in range(N):
            if (parent[i] == -1):
                root = i
                break

        depth = [0 for _ in range(N)]
        for x in leaf:
            now = x
            depth[now] = 0
            while (parent[now] != -1):
                depth[parent[now]] = max(depth[parent[now]], depth[now]+1)
                now = parent[now]

        ans = 0
        for i in range(N):
            d = list()
            for x in children[i]:
                d.append(depth[x])
            d.sort()
            if (len(children[i]) == 1):
                ans = max(ans, d[-1]+1)
            elif (len(children[i]) > 1):
                ans = max(ans, d[-1]+d[-2]+2)
        print(ans)
    except:
        break
分享本文 Share with friends