題目連結: https://tioj.ck.tp.edu.tw/problems/1152
# 內容
給定一個裸樹，求最遠的兩點距離。
# 思路
這是一題裸裸的樹直徑題，不難發現 dfs 一次找到最遠點，再用那個點當作第二次 dfs 的根，再找一次最遠點，不外乎就是樹直徑
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
#define PB push_back | |
typedef pair<int,int> PII; | |
#define FF first | |
#define SS second | |
const int N = 10000 + 5; | |
vector<int> G[N]; | |
void dfs(int,int,int,PII&); | |
int main(){ | |
ios_base::sync_with_stdio(0);cin.tie(0); | |
int n; cin>>n; | |
for(int i=0;i<n;i++){ | |
int x; | |
while(cin>>x and x!=-1){ | |
G[i].PB(x); | |
G[x].PB(i); | |
} | |
} | |
PII ans = {0, -1}; | |
dfs(0, 0, 0, ans); | |
ans.SS = -1; | |
dfs(ans.FF, ans.FF, 0, ans); | |
cout<<ans.SS<<'\n'; | |
return 0; | |
} | |
void dfs(int w, int f, int sum, PII& ret){ | |
if(sum > ret.SS) ret = {w, sum}; | |
for(auto i: G[w]){ | |
if(i==f) continue; | |
dfs(i, w, sum+1, ret); | |
} | |
} |
