c++Kruskal算法函数

以下是一个基于C++的Kruskal算法函数示例：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=500010; // 定义最大点数和最大边数
int n,m,ans;
int fa[maxn],r[maxn]; // 并查集数组，r[i]表示以i为根的树的高度
struct edge{int u,v,w;}e[maxm]; // 存储边的结构体数组
bool cmp(edge a,edge b){return a.w<b.w;} // 按照边权从小到大排序的比较函数
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} // 查找x所在的集合的根节点
void merge(int x,int y){ // 合并x和y所在的集合
    x=find(x),y=find(y);
    if(x==y)return;
    if(r[x]<r[y])swap(x,y);
    fa[y]=x;
    if(r[x]==r[y])r[x]++;
}
void kruskal(){
    sort(e+1,e+m+1,cmp); // 将所有边按照边权从小到大排序
    for(int i=1;i<=n;i++)fa[i]=i,r[i]=0; // 初始化并查集
    for(int i=1;i<=m;i++){ // 枚举所有边
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(find(u)==find(v))continue; // 如果u和v已经在同一个集合中，说明加入这条边会形成环，跳过
        merge(u,v); // 合并u和v所在的集合
        ans+=w; // 累加边权
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); // 读入边
    kruskal(); // 进行Kruskal算法
    printf("%d",ans); // 输出最小生成树的边权之和
    return 0;
}

这个函数的主要思路是将所有边按照边权从小到大排序，然后枚举所有边，判断当前边的两个端点是否已经在同一个集合中，如果不在同一个集合中，就合并这两个集合，并将当前边的边权累加到最小生成树的边权之和中。最后输出最小生成树的边权之和。