Kruskal 最小生成树

#include <stdio.h>
#include <algorithm>
#define MAX 100
#define MAX_EDG 1000 

using namespace std;

typedef struct Node{
    int u;
    int v;
    int w;
}Node;


Node map[MAX_EDG];    //注意：顶点数和边数的最大值是不一样的，要分别定义 
int father[MAX];    //自己的父亲 
int rank_[MAX];        //秩 

bool cmp(Node a, Node b){
    return a.w < b.w;    //从小到大 升序 
}

int find(int x){
    if(father[x]==x)    return x;
    else return    father[x]=find(father[x]);        //向上找父亲直到找到根节点 
}

void unite(int x, int y){
    if(find(x) == find(y))    return;
    else{
        int x_root=find(x);
        int y_root=find(y);
        if(rank_[x_root] > rank_[y_root])            //按秩合并   //比较的是树根x_root和y_root的秩 ，不是x和y的 
            father[y_root]=x_root;
        else if(rank_[y_root] > rank_[x_root])
            father[x_root]=y_root;
        else{                            //两个树根的秩一样的话，任意合并到其中一个树根中，然后秩++ 
            father[x_root]=y_root;
            rank_[y_root]++;
        }    
    }
}

void init(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;        //自己是自己的父亲 
        rank_[i]=0;            //初始高度为0 
    }
}

int main(){
    int n,m;
    int count,sum;
    int u,v,w;
    while(scanf("%d %d",&n,&m)!=EOF){
        init(n);
        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);            //sort排序，由小到大 
        count=0;
        sum=0;
        for(int i=1;i<=m;i++){
            if(count==n-1)    break;            //n个顶点被n-1条边连接就跳出 
            u=map[i].u;
            v=map[i].v;
            w=map[i].w;
            if(find(u)!=find(v)){        //如果不在同一个子树就合并 
                unite(u,v);
                count++;
                sum+=w;
            }
        }
        printf("%d\n",sum);         //sum是n-1条边的边权和 
    }
    return 0;
}