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;
 }