h032 - 201603_q4 血緣關係（單筆測資版）
題目描述
題目給定一個包含 n 個節點的樹，要求找出樹中最長路徑的長度。樹以鄰接表的形式表示，輸入包含 n-1 條邊，表示節點之間的連接關係。
解題思路
這題的核心是找到樹的直徑。直徑是指樹中最長路徑的長度。解題思路是先從任意一個節點出發進行深度優先搜尋 (DFS)，找到距離該節點最遠的節點。然後，再從這個最遠的節點出發進行另一次 DFS，找到距離該節點最遠的節點。這兩次 DFS 的路徑長度就是樹的直徑。
程式碼中，dfs 函數用於進行深度優先搜尋。第一次 dfs 從節點 0 開始，找到距離節點 0 最遠的節點，並記錄其深度 ma。第二次 dfs 從第一次 dfs 找到的最遠節點 rt[ma] 開始，再次進行深度優先搜尋，最終輸出 ma，即樹的直徑。
複雜度分析
- 時間複雜度: O(n)，其中 n 是節點的數量。因為需要進行兩次 DFS，每次 DFS 都會遍歷所有節點和邊。
- 空間複雜度: O(n)，主要用於儲存鄰接表
E和has陣列，以及遞迴呼叫堆疊。
程式碼
#include <iostream>
#include <vector>
using namespace std;
int n,x,y,rt[100005],has[100005],ma;
vector <int> E[100005];
void dfs(int it,int stp){
if(has[it])return;
ma=max(ma,stp);
has[it]=1;
rt[stp]=it;
for(int i=0;i<E[it].size();++i){
dfs(E[it][i],stp+1);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
ma=0;
for(int i=0;i<n;++i){
has[i]=0;
E[i].clear();
}
for(int i=0;i<n-1;++i){
cin >> x >> y;
E[x].push_back(y);
E[y].push_back(x);
}
dfs(0,0);
for(int i=0;i<n;++i){
has[i]=0;
}
dfs(rt[ma],0);
cout << ma << "\n";
}
}