最小生成树

①Kuskal算法（克鲁斯卡尔）

时间复杂度为O(m log m)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct edge
{
	int u,v,w;
};
edge a[maxn];
bool cmp(edge f1,edge f2)
{
	return f1.w<f2.w;
}
int fa[5010];
int checkk(int k)
{
	if(fa[k]==k)	return k;
	return fa[k]=checkk(fa[k]);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=n;i++)	fa[i]=i;
	long long ans=0,cnt=n;
	for(int i=1;i<=m;i++)
	{
		if(cnt==1)	break;
		int x=checkk(a[i].u),y=checkk(a[i].v);
		if(x!=y)
		{
			ans+=a[i].w;
			fa[x]=y;
			cnt--;
		}
	}
	printf("%lld\n",ans);
    return 0;
}