a523 - 12442 - Forwarding Emails
題目描述
題目描述了火星人轉寄電子郵件的方式。酋長想找到一個起始點，使得從該點開始轉寄的郵件能夠觸及最多的火星人。輸入給定一個火星人網絡，表示誰會將郵件轉寄給誰。目標是找到最佳的起始火星人，以最大化郵件的傳播範圍。如果有多個起始點可以達到最大傳播範圍，則選擇編號最小的那個。
解題思路
這題可以建模成一個有向圖，其中每個火星人是一個節點，u 轉寄給 v 則表示從 u 到 v 存在一條有向邊。問題轉化為在圖中找到一個起始節點，使得從該節點出發的深度優先搜索 (DFS) 能夠訪問最多的節點。
程式碼使用 DFS 來遍歷圖。對於每個節點，如果該節點尚未被訪問過，則啟動一次 DFS。在 DFS 過程中，記錄訪問的節點數量。然後，比較每次 DFS 訪問的節點數量，找到訪問節點數量最多的起始節點。如果有多個起始節點具有相同的最大訪問數量，則選擇編號最小的那個。used 陣列用於標記已訪問的節點，防止無限循環。c 陣列用於標記是否已經計算過該節點的連通分量大小。
複雜度分析
- 時間複雜度: O(N * (N + E))，其中 N 是火星人的數量，E 是轉寄關係的數量。最壞情況下，需要對每個節點執行一次 DFS，而每次 DFS 的時間複雜度為 O(N + E)。
- 空間複雜度: O(N)，主要用於儲存
a、c和used陣列，以及 DFS 的遞迴堆疊。
程式碼
#include <iostream>
#include <memory.h>
using namespace std;
int t,n,a[100005],x,y,times;
bool c[100005],used[100005];
void dfs(int n){
if(used[n])return;
++times;
c[n]=used[n]=1;
dfs(a[n]);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> n;
for(int i=1;i<=n;++i){
a[i]=i;
used[i]=c[i]=0;
}
for(int i=1;i<=n;++i){
cin >> x >> y;
a[x]=y;
}
int ans=0,ansm=0;
for(int i=1;i<=n;++i){
memset(used,0,n+1);
times=0;
if(c[i]==0){
dfs(i);
}
if(times>ans){
ans=times;
ansm=i;
}
}
cout << "Case " << ca << ": " << ansm << "\n";
}
}