Kruskal算法求最小生成树
代码实现
/*
f[maxn]:数组存的是father
Node{}结构体:存放的是边
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int f[maxn];
struct Node{
int u,v,w;
}node[maxn];
int n,m;
bool cmp(Node a, Node b){
return a.w < b.w;
}
void Init(int n){
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++){
cin >> node[i].u >> node[i].v >> node[i].w;
}
sort(node+1,node+1+m,cmp);
}
int find(int x){
return x==f[x]?x:f[x] = find(f[x]);
}
void Kruskal(){
int sum = 0;
int cnt = 0;
for(int i = 1; i <= m; i++){
int u = find(node[i].u);
int v = find(node[i].v);
if(u!=v){
f[u] = f[v];
sum += node[i].w;
cnt++;
}
if(cnt==n-1){
cout<<sum<<endl;
return ;
}
}
}
int main(void){
cin >> n >> m;
Init(n);
Kruskal();
return 0;
}