Kruskal算法——最小生成树

#include <bits/stdc++.h>
using namespace std;
int flag;
const int maxn=100000+15;
const int maxm=100000+15;
struct Edge
{
    int x,y,z;
}edge[maxm];
int n,m;
bool cmp(Edge a,Edge b)
{
    return a.z<b.z;
}
int top[maxn];
int rec[maxn];
int found(int x)
{
    if (top[x]==x) return x;
    return top[x]=found(top[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
     } 
    sort(edge+1,edge+m+1,cmp);  //O(mlogm)
    for (int i=1;i<=n;i++) top[i]=i;
    int ans=0;
    int tot=0;
    for (int i=1;i<=m;i++)
    {
        int fx=found(edge[i].x),fy=found(edge[i].y);
        if (fx!=fy)
        {
            tot++;
            rec[i]=tot;
            ans+=edge[i].z;
            top[fx]=fy;
            if (tot==n-1) break;    
        }
    }
    cout<<ans;
    return 0;
 } 

´Kruskal算法主要分为两步：

´给所有边按照边权从小到大的顺序排序；

´从小到大依次考虑每条边(u,v)（最开始没有任何的边）:

´如果u与v已经连通了，那么加入(u,v)后会出现环，不添加；

´如果u与v没有连通，那么加入(u,v)使其连通。

´然后，对于判断是否联通，我们可以通过并查集来维护。