克鲁斯卡尔最小生成树c++

克鲁斯卡尔算法是一种用来求加权无向图的最小生成树的贪心算法。其基本思路是将图中的所有边按照权值从小到大排序，依次加入生成树中，如果加入一条边会形成环，则不加入该边。直到加入了n-1条边或者所有边都被考虑过。

以下是Kruskal最小生成树算法的C++实现示例：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005,MAXM=200005;
int n,m,f[MAXN],ans,cnt;
struct Edge{
    int u,v,w;
}e[MAXM];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    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<=m;i++){
        int fu=find(e[i].u),fv=find(e[i].v);
        if(fu==fv)continue;
        ans+=e[i].w;
        f[fu]=fv;cnt++;
        if(cnt==n-1)break;
    }
    cout<<ans<<endl;
    return 0;
}