【題目敘述】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