b967 - 4. 血緣關係
題目描述
題目要求找出一個家族關係圖中最遠的血緣距離。家族關係圖以樹狀結構表示，其中一個節點是祖先，其他節點是其後代。血緣距離定義為兩個節點之間的路徑長度。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。首先，我們需要建立一個鄰接表來表示家族關係圖。然後，我們從根節點 (節點 0) 開始進行 DFS，找到距離最遠的節點。接著，再次從這個最遠的節點開始進行 DFS，找到從該節點到其他節點的最長路徑，這就是最遠的血緣距離。
具體步驟如下：
- 建立鄰接表
E，其中E[i]儲存節點i的所有子節點。 - 進行第一次 DFS，從根節點 0 開始，找到距離最遠的節點，並記錄其深度
ma。 - 使用
rt[ma]記錄第一次 DFS 找到的最遠節點。 - 清空
has陣列，然後從rt[ma]再次進行 DFS，找到從該節點到其他節點的最長路徑，即最遠的血緣距離。
複雜度分析
- 時間複雜度: O(N)，其中 N 是家族成員的數量。因為 DFS 遍歷了圖中的所有節點和邊。
- 空間複雜度: O(N)，主要用於儲存鄰接表
E、has陣列和rt陣列。
程式碼
#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";
}
}