acwing859. Kruskal算法求最小生成树

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;

int p[N],n,m;
struct Edge{
    int a,b,w;
    bool operator <(const Edge &W)const{
        return w<W.w;
    }
}edges[M];

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int Kruskal(){
    int res=0,cnt=0;
    sort(edges,edges+m);
    for(int i=1;i<=n;i++)p[i]=i;
    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b;
        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            res+=edges[i].w;
            cnt++;
        }
    }
    
    if(cnt<n-1)return INF;
    else return res;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }
    int res=Kruskal();
    if(res==INF)puts("impossible");
    else cout<<res<<endl;
    
    
    
    return 0;
}