Kruskal算法84pts求助

P3366 【模板】最小生成树

zzxzzxCCC @ 2023-08-15 20:35:49

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
struct rec{
    int x,y,z;
}edge[500010];
bool operator <(rec a,rec b){
    return a.z<b.z;
}
int fa[100010],n,m;
int getfa(int x){
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
int main(){
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++){
        int x=getfa(edge[i].x),y=getfa(edge[i].y);
        if(x==y) continue;
        fa[x]=y;
        ans+=edge[i].z;
    }
    if(ans==0) { printf("orz");return 0;}
    printf("%d",ans);
    return 0;
}

by yqr123YQR @ 2023-08-15 20:39:03

ans = 0 不一定说明不连通啊


by yqr123YQR @ 2023-08-15 20:39:58

应该直接循环统计最后剩下了几个连通块


by 蒟蒻的我orz @ 2023-08-22 17:01:59

int cnt=0;
for(int i=1;i<=m;i++){
        int x=getfa(edge[i].x),y=getfa(edge[i].y);
        if(x==y) continue;
        fa[x]=y;
        ans+=edge[i].z;
        cnt++;
        if(cnt==n-1)break;
    }
    if(cnt!=n-1) { printf("orz");return 0;}
    printf("%d",ans);

|