最小生成树kruskal求法：对边权排序之后，用并查集去链接集合，直到剩下一个集合结束

kruskal算法：
//第一步：给所有边按照从小到大的顺序排列
//知识点：联通分量的概念：
//（1）在无向图中，如果顶点Vi到顶点Vj有路径，则称顶点Vi和Vj联通
//（2）如果无向图中任意两个顶点之间都连通，则称为连通图
//（3）如果不是连通图，则图中的 极大连通子图 称为连通分量

接下来要从小到大依次考察每条边（u,v)
//（1）u和v在同一个连通分量中，那么加入(u,v)后会形成环，因此不能选择
//（2）如果在不同的连通分量里面，那么加入后一定是最优的

//一开始要初始化连通分量，让每个点都自成一个独立的连通分量
例题：洛谷：P3366:https://www.luogu.com.cn/problem/P3366

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;

using namespace std;
struct edge
{
    ll u,v,w;
}e[200010];

bool cmp(edge &a,edge &b)
{
    return a.w<b.w;
}

ll f[200005],n,m,ans,cnt;
ll find(ll x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
void kruskal()
{
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++)
    {
        ll u=e[i].u;
        ll v=e[i].v;
        ll w=e[i].w;
        ll fu=find(u), fv=find(v);
        if(fu==fv) continue; //如果两者在一个连通图里面，continue
        ans+=w;
        f[fv]=fu;//一定是将两者的祖先连在一起
        cnt++;
        if(cnt==n-1) break; //最小生成树只有n-1条边
    }
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    //每个点都自成一个连通量

    for(int i=0;i<m;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w; //输入两个端点和边的权值
    }
    kruskal();
    if(cnt!=n-1)
    {
        printf("orz");
    }
    printf("%lld",ans);
    return 0;
}