Krusksal

传送门
最小生成树板子题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int n , m;
struct node{
    int u , v;
    ll w;
}edge[N];
bool cmp(node a, node b){
    return a.w < b.w;
}
int fa[N];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
ll kruskal(){
    for(int i = 1 ; i <= n ; i++) fa[i] = i;
    sort(edge + 1, edge + 1 + m , cmp);
    ll ans = 0;
    ll cnt = 0;
    for(int i =  1; i <= m ; i++){
        ll x = find(edge[i].u);
        ll y = find(edge[i].v);
        if(x != y){
            fa[x] = y;
            cnt++;
            ans = max(ans , edge[i].w);
        }
        if(cnt == n - 1) break;
    }
    if(cnt == n - 1) return ans;
    else return -1;
}
int main()
{

    cin>>n>>m;
    for(int i = 1; i <= m ; i++){
        scanf("%lld %lld %lld", &edge[i].u , &edge[i].v , &edge[i].w);
    }
    cout<<kruskal()<<endl;
    return 0;
}