最小生成树--kruskal

//n个城市互相连通 最少n-1条路
//最小生成树--稀疏图  kruskal
//每次选取权值最小的边
#include<bits/stdc++.h>
using namespace std;
int n,m; //n个顶点 m条边
int fa[5005];
struct edge { //存储边
	int u,v,w;
} e[200005];
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int find(int x) { //找父节点 
	if(fa[x]==x) {
		return x;
	} else {
		fa[x]=find(fa[x]);
		return fa[x];
	}
}
void kruskal() {
	int cnt=0,ans=0;
	for(int i=1; i<n; i++) { //初始化并查集
		fa[i]=i;
	}
	sort(e,e+m,cmp);//按边权排序 
	for(int i=0; i<m; i++) {
		int a=find(e[i].u);
		int b=find(e[i].v);
		int c=e[i].w;
		if(a!=b){//ab不在同一集合 
			fa[a]=b;
			cnt++;
			ans+=c;
		}
	}
	cout<<ans<<endl;
}
	int main() {
		cin>>n>>m;
		for(int i=0; i<m; i++) {
			int a,b,c;
			cin>>a>>b>>c; 
			e[i]={a,b,c};//从u到v有一条权值为w的边
		}
		kruskal();
		return 0;
	}