a584_2 - Family Tree Distance
題目描述
題目給定一個家族樹的關係，以父子關係表示。輸入包含家族成員的父子關係列表，以及兩個家族成員的名字。要求計算這兩個家族成員之間的距離，距離定義為從其中一個成員到共同祖先的距離加上從共同祖先到另一個成員的距離。
解題思路
這題的核心是建立一個家族樹的表示，並計算兩個節點之間的距離。程式使用 map<string, string> p 來儲存父子關係，其中 key 是子節點，value 是父節點。程式首先讀取父子關係，建立這個 p map。然後，程式計算第一個輸入成員到根節點（"root"）的距離，並儲存在 map<string, int> fd 中。接著，程式從第二個輸入成員開始，向上追溯，直到找到在 fd 中存在的節點，計算追溯的步數，並將其加到 fd 中儲存的距離上，得到最終的距離。
複雜度分析
- 時間複雜度: O(N + M)，其中 N 是家族成員的數量，M 是追溯到共同祖先所需的步數。建立
pmap 需要 O(N) 的時間，計算距離需要 O(M) 的時間。 - 空間複雜度: O(N)，主要用於儲存
pmap 和fdmap。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,it,f,d,ans;
string input,goal;
map <string,string> p;
map <string,int> fd;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
getline(cin,input);
for(int ca=0;ca<n;++ca){
getline(cin,input);
input+=' ';
int s=0;
string tmp,h;
for(int i=0;i<input.length();++i){
if(input[i]!=' '){
tmp+=input[i];
}
else{
if(s==0){
s=1;
h=tmp;
if(p.find(h)==p.end()){
p[h]="root";
}
}
else{
p[tmp]=h;
}
tmp.clear();
}
}
}
cin >> input >> goal;
string tmp=input;
fd[input]=ans=0;
while(tmp!="root"){
tmp = p[tmp];
fd[tmp]=++ans;
//cout << fd[tmp] << " " << tmp << "\n";
}
tmp = goal;
ans=0;
while(fd.find(tmp)==fd.end()){
tmp = p[tmp];
++ans;
}
cout << ans+fd[tmp];
}