题解 | #寻宝#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge{
    int u,v,w;
    bool operator<(const Edge& other)const{
        return w<other.w;
    }
};

vector<int> parent,rank_set;

int find(int x){
    if(parent[x]!=x)parent[x]=find(parent[x]);
    return parent[x];
}

void unite(int x,int y){
    int rootX=find(x);
    int rootY=find(y);
    if(rootX!=rootY){
        if(rank_set[rootX]>rank_set[rootY])
            parent[rootY]=rootX;
        else if(rank_set[rootX]<rank_set[rootY])
            parent[rootX]=rootY;
        else{
            parent[rootY]=rootX;
            rank_set[rootX]++;
        }
    }
}

int main() {
    int N,M;
    cin>>N>>M;
    vector<Edge> edges(M);
    for(int i=0;i<M;++i){
        int P,Q,K;
        cin>>P>>Q>>K;
        edges[i]={P,Q,K};
    }
    sort(edges.begin(),edges.end());
    parent.resize(N+1);
    rank_set.resize(N+1,0);
    for(int i=1;i<=N;++i)
        parent[i]=i;
    int max_edge_in_mst=0;
    int edges_used=0;
    for(const auto&edge:edges){
        if(find(edge.u)!=find(edge.v)){
            unite(edge.u,edge.v);
            max_edge_in_mst=edge.w;
            edges_used++;
            if(edges_used==N-1)
                break;
        }
    }
    cout<<max_edge_in_mst<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")