Kruskal模板(C++版)

hiho1098
并查集 对边权排序 贪心取边权小的边

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
const int M=1e6+50;
int n,m,u,v,w;
int p[N];
struct Edge{
   
    int u,v,w;
}edge[M];
int cnt;
void addEdge(int u,int v,int w){
   
    edge[cnt++]=Edge{
   u,v,w};
}
bool cmp(Edge a,Edge b){
   
    return a.w<b.w;
}
int find(int x){
   
    return p[x]==x ? x : p[x]=find(p[x]);
}
int Kruskal(){
   
    int ans=0;
    int c=0;
    for(int i=0;i<=n;i++){
   
        p[i]=i;
    }
    sort(edge,edge+cnt,cmp);
    for(int i=0;i<cnt;i++){
   
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        int fa=find(u);
        int fb=find(v);
        if(fa!=fb){
   
            ans+=w;
            p[fa]=fb;
            c++;
        }
        if(c==n-1){
   
            break;
        }
    }
    if(c<n-1){
   
        //不连通
        return -1;
    }
    return ans;
}
int main(void){
   
    scanf("%d%d",&n,&m);
    cnt=0;
    while(m--){
   
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    int ans=Kruskal();
    printf("%d\n",ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
06-01 21:50
已编辑
天津理工大学 Java
点赞 评论 收藏
分享
06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务