图论板子 最小生成树

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<string>
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int, int> pr;
typedef long long ll;
#define fi first
#define se second
#define me(x) memset(x, -1, sizeof(x))
#define mem(x) memset(x, 0, sizeof(x))
#define MAXN 500000+5
#define NIL -1
struct node
{
    int u, v, w;
}edge[MAXN];
bool cmp(node a, node b)
{
    if(a.w==b.w && a.u==b.u) return a.v<b.v;
    if(a.w==b.w) return a.u<b.u;
    return a.w<b.w;
}
int p[MAXN];//存祖先  记录每个点的前导点
int ans, n, m;

int Find(int x) //查找根节点
{
    int r=x;
    while(p[r]!=r) //根节点的上级节点为本身
        r=p[r];
    //r为根节点
    int i=x, j;
    while(p[i]!=r)//until p[p[i]]==r 路径压缩 不断更新i的上级节点为根节点
    {
        j=p[i];

        p[i]=r;   //r为根

        i=j;
    }             // 1 --> 3 --> 4 --> 5
    return r;
}

int mix() //合并 联通
{
    for(int i=0; i<m; i++)
    {
        int fx=Find(edge[i].u), fy=Find(edge[i].v);
        if(fx!=fy)
            ans+=edge[i].w, p[fx]=fy;
    }
}
int main()
{
    int i, j, k;
    while(cin>>n>>m)
    {
        ans=0;
        for(i=1; i<=n; i++)
            p[i]=i;        //初始化每个点的父节点为本身
        for(i=0; i<m; i++)
            cin>>edge[i].u>>edge[i].v>>edge[i].w;
        sort(edge, edge+m, cmp);
        mix();
        cout<<ans<<endl;
    }
}