最小生成树之Kruskal

蒟蒻飘过...很基础的一个算法，主要为了加深理解，而且蒟蒻的代码画风很清真

从这篇博客学习了不少，而且配了很详细的图解 点击打开链接

Kruskal是寻找最小生成树的算法之一，按边权贪心

大致算法如下：

     1）原图有n个顶点，m条边。将m条边从小到大排序

     2）新建一个与原图有相同节点而没有边的图（不用建），从最小的边开始遍历，将新图中已经连上的节点打上标记

     3）对于每条边，检查连接后是否会成环（用并查集，如果连接之前两端的标记就是一样的，则不可连）

     4）记录已连接的边的条数，当连上n-1条边时，n个点都在树上了，最小生成树建成

附代码（只有并查集用了路径压缩画风不清真...第一次听学长讲的就长这样...点击打开链接上的并查集很清真）

洛谷 3366

#include <cstdio>
#include <algorithm>
using namespace std;
int f[5005];                         //并查集标记记录 
struct edge{
    int u,v,w;                       //储存边的信息，u,v为始、终点，w为权值 
}e[200010];

int ff(int x){
	return f[x]==x?x:f[x]=ff(f[x]);  //并查集，找到最初始的标记值 
}

void merge(int x,int y){
    if(ff(x)!=ff(y))f[ff(x)]=ff(y);  //如果不在同一个联通块，就合并 
}

bool cmp(edge x,edge y){
    return x.w<y.w;                  //返回权值较小的边，使排序从小到大 
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    }                                                //输入 
    sort(e+1,e+m+1,cmp);                             //排序 
    int num=0,ans=0; 
    for(int i=1;;i++){
        if(ff(e[i].u)!=ff(e[i].v)){                  //如果不成环，即未联通 
            merge(e[i].u,e[i].v);                    //合并（联通） 
            ans+=e[i].w;                             //总权值加上新边权值 
            num++;
            if(num==n-1)break;                       //已连上n-1条边时，跳出循环 
        }
    }
    printf("%d",ans);
}