f506 - 11747 - Heavy Cycle Edges
題目描述
題目要求找出一個無向圖中，在構建最小生成樹的過程中，所有被移除的邊的權重。移除的邊是那些屬於循環，且在循環中權重最大的邊。如果圖中沒有循環，則輸出 "forest"。
解題思路
本題的核心思想是利用 Kruskal 算法的思想，但反向操作。Kruskal 算法是從最小的邊開始添加，直到形成一個最小生成樹。而本題是從所有邊開始，然後逐步移除循環中權重最大的邊。
- 初始化: 使用 Union-Find 資料結構來追蹤圖的連通性。初始時，每個節點都是一個獨立的集合。
- 排序: 將所有邊按照權重從小到大排序。
- 迭代: 遍歷排序後的邊。
- 如果邊的兩個端點不在同一個集合中，則將它們合併，表示添加了這條邊。
- 如果邊的兩個端點在同一個集合中，則表示添加這條邊會形成一個循環。此時，這條邊就是循環中權重最大的邊，需要移除，並將其權重記錄下來。
- 輸出: 將所有被移除的邊的權重按照從小到大的順序輸出。如果沒有移除任何邊，則輸出 "forest"。
複雜度分析
- 時間複雜度: O(M log M + M α(N))，其中 M 是邊的數量，N 是節點的數量，α(N) 是反阿克曼函數，在實際應用中可以視為常數。排序邊需要 O(M log M) 的時間，Union-Find 操作（find 和 union）平均時間複雜度為 O(α(N))，總共需要 M 次操作。
- 空間複雜度: O(N + M)，其中 N 是節點的數量，M 是邊的數量。需要 O(N) 的空間來儲存 Union-Find 資料結構，O(M) 的空間來儲存邊。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int fa[1005],n,m,k;
pair <int,pair <int,int> > edge[30005];
int ff(int x){
if(fa[x]==x)return x;
return fa[x]=ff(fa[x]);
}
void merge(int x,int y){
x=ff(x);
y=ff(y);
if(x==y)return;
fa[x]=y;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
int ac=0;
for(int i=0;i<=n;++i){
fa[i]=i;
}
for(int i=0;i<m;++i){
cin >> edge[i].second.first >> edge[i].second.second >> edge[i].first;
}
sort(edge,edge+m);
for(int i=0;i<m;++i){
if(ff(edge[i].second.first)!=ff(edge[i].second.second)){
merge(edge[i].second.first,edge[i].second.second);
}
else{
if(ac)cout << " ";
cout << edge[i].first;
ac=1;
}
}
if(ac==0){
cout << "forest";
}
cout << "\n";
}
}