a584 - 2. 親等關係
題目描述
題目要求計算兩個人的親等關係，親等關係定義為在樹狀圖中連接兩個人的連結數。輸入包含建立樹狀圖的父子關係資料，以及要查詢親等關係的兩個人的名字。
解題思路
本題可以將親等關係問題建模為圖論中的最短路徑問題。其中，人名作為圖的節點，父子關係作為圖的邊。可以使用廣度優先搜尋 (BFS) 演算法來計算兩個節點之間的最短路徑長度，即親等關係。
- 建立一個圖，使用
map儲存人名到節點編號的映射。 - 使用鄰接矩陣
a儲存圖的邊。 - 使用 BFS 演算法從起點人名對應的節點開始搜尋，直到到達終點人名對應的節點。
- 在 BFS 過程中，記錄每個節點的距離，即從起點到該節點的連結數。
- 輸出終點節點的距離，即兩個人的親等關係。
複雜度分析
- 時間複雜度: O(V + E)，其中 V 是節點數（人數），E 是邊數（父子關係數）。在最壞情況下，需要遍歷所有節點和邊。
- 空間複雜度: O(V)，主要用於儲存圖的鄰接矩陣、
map和 BFS 隊列。
程式碼
#include <iostream>
#include <map>
#include <queue>
using namespace std;
int n,it,f,d,ans;
string input,goal;
map <string,int> p;
queue <int> fd;
bool a[501][501];
int used[25001];
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]=it++;
}
}
else{
if(p.find(tmp)==p.end()){
p[tmp]=it++;
}
a[p[h]][p[tmp]]=a[p[tmp]][p[h]]=1;
}
tmp.clear();
}
}
}
cin >> input >> goal;
f=p[input];
used[f]=0;
fd.push(f);
while(fd.empty()==0){
int x = fd.front();
fd.pop();
for(int i=0;i<it;++i){
if(a[x][i]&&used[i]==0){
used[i]=used[x]+1;
fd.push(i);
}
}
}
cout << used[p[goal]];
}