图的最小生成树---克鲁斯卡尔(Kruskal)算法

关于Kruskal算法，这里有一篇博客：最小生成树之Kruskal算法，我总结一下重点：

这是最小生成树的另一种算法，要求总长度之和最短，那么先把图的路径的权值从小到大排列一下，最终连成n-1条边。按照排列好的顺序依次连线，在连线的过程中可能遇到有些点已经联通了,这时我们需要用上并查集来判断两个顶点是否已经连通。

给一组测试数据：

输入：

6 9  2 4 11  3 5 13  4 6 3  5 6 4  2 3 6  4 5 7  1 2 1  3 4 9  1 3 2  
输出：
19
代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <string>#include <iostream>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mem(a,b) memset(a,b,sizeof(a))#define N 100+20#define M 100000+20#define MOD 1000000000+7#define inf 0x3f3f3f3fusing namespace std;struct node{    int u;    int v;    int w;} map[10];int n,m;int f[7]= {0},sum=0,cnt=0; //并查集用int getf(int v)//并查集查找祖先{    if(f[v]==v)        return v;    else    {        //路径压缩        f[v]=getf(f[v]);        return f[v];    }}//并查集合并两个子集int mix(int v,int u){    int t1,t2;    t1=getf(v);    t2=getf(u);    if(t1!=t2)//判断两个点是否在同一个集合中    {        f[t2]=t1;        return 1;    }    return 0;}bool cmp(node x,node y){    return x.w<y.w;}int main(){    scanf("%d%d",&n,&m);    for(int i=1; i<=m; i++)        scanf("%d%d%d",&map[i].u,&map[i].v,&map[i].w);    sort(map+1,map+m+1,cmp);    //并查集初始化    for(int i=1; i<=n; i++)        f[i]=i;    //克鲁斯卡尔(Kruskal)算法的核心内容    for(int i=1; i<=m; i++) //从小到大枚举边    {        //判断一条边的两个顶点是否联通，就是判断是否在同一个集合中        if(mix(map[i].u,map[i].v))//没有连通的话就选用这条边        {            cnt++;            sum+=map[i].w;        }        if(cnt==n-1)//选了n-1条边后退出循环            break;    }    PRintf("%d",sum);    return 0;}