C++编码实现克鲁斯卡尔算法
时间: 2023-11-30 11:43:42 浏览: 84
以下是C++编码实现克鲁斯卡尔算法的示例:
```c++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, m, fa[MAXN];
struct Edge {
int u, v, w;
}e[MAXN];
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + m + 1, cmp);
for(int i = 1; i <= n; i++) {
fa[i] = i;
}
int cnt = 0, ans = 0;
for(int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v, w = e[i].w;
int x = find(u), y = find(v);
if(x != y) {
fa[x] = y;
cnt++;
ans += w;
}
if(cnt == n - 1) break;
}
cout << ans << endl;
return 0;
}
```
阅读全文