f503 - 1056 - Degrees of Separation
題目描述
題目給定一個網路中 P 個人和 R 種關係，每種關係連接兩個人。要求計算這個網路中任意兩個人之間的最大距離（最少需要經過多少關係才能連接）。如果網路不連通，則輸出 "DISCONNECTED"。
解題思路
這題可以建模成一個圖，其中每個人是一個節點，每種關係是一條邊。邊的權重都是 1。然後使用 Floyd-Warshall 演算法計算所有節點對之間的最短路徑。Floyd-Warshall 演算法可以有效地計算圖中所有節點對之間的最短路徑。 首先，將人名映射到整數 ID，以便在鄰接矩陣中表示圖。然後，初始化鄰接矩陣，將直接關係的距離設為 1，其他設為 INF。接著，執行 Floyd-Warshall 演算法，計算所有節點對之間的最短路徑。最後，遍歷最短路徑矩陣，找到最大距離。如果存在 INF，則表示圖不連通，輸出 "DISCONNECTED"。
複雜度分析
- 時間複雜度: O(N^3)，其中 N 是人的數量。Floyd-Warshall 演算法的時間複雜度為 O(N^3)。
- 空間複雜度: O(N^2)，其中 N 是人的數量。需要一個 N x N 的鄰接矩陣來存儲圖。
程式碼
#include <iostream>
#include <map>
#define INF 500
using namespace std;
int a[55][55],n,m,ca;
string x,y;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
int id=0,ac=1,mi=0;
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
a[i][j]=INF;
if(i==j)a[i][j]=0;
}
}
map <string,int> mp;
while(m--){
cin >> x >> y;
if(mp.find(x)==mp.end()){
mp[x]=id++;
}
if(mp.find(y)==mp.end()){
mp[y]=id++;
}
a[mp[x]][mp[y]]=a[mp[y]][mp[x]]=1;
}
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(a[i][j]==INF){
ac=0;
}
else{
mi=max(a[i][j],mi);
}
}
}
cout << "Network " << ++ca << ": ";
if(ac){
cout << mi << "\n";
}
else{
cout << "DISCONNECTED\n";
}
cout << "\n";
}
}