Krustral算法求解最小生成树 C++实现

#include
#include
using namespace std;
const int N=100010,M=200010,INF=0x3f3f3f3f;
int n,m;
int p[N];
struct Edge{
    int a,b,w;
}edges[M];
int res,cnt;
 
int find(int a){
    if(p[a]!=a) p[a]=find(p[a]);
    return p[a];
}
bool cmp(struct Edge a,struct Edge b){
    return a.w
}
 
int krustral(){
    sort(edges,edges+m,cmp);
    for(int i=0;i
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            res += w;
            cnt += 1;
        }
    }
    return cnt-1 ? INF :res;
}
 
 
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i]={a,b,c};
    }
    for(int i=1;i<=n;i++) p[i]=i;
    
    int t=krustral();
    if(t==INF) puts("impossible");
    else printf("%d",t);
}