Minimum Spanning Tree (MST) - Kruskal

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

#define siz 1000005

typedef long long ll;

int N,E;

int p[siz],rank[siz];



struct data{

    int u,v,c;

}a[siz];



void makeSet(int n){

    p[n]=n;

    rank[n]=0;

}



int findSet(int x){

    if(x!=p[x]) return p[x]=findSet(p[x]);

    return p[x];

}



void Union(int x, int y){

    if(rank[x]>rank[y]) p[y]=x;

    else{

        p[x]=y;

        if(rank[x]==rank[y]) rank[y]+=1;

    }

}



bool cmp(data a, data b){

    if(a.c<b.c) return true;

    return false;

}



int main()

{

    int u,v,c;

    //freopen("input.txt","r",stdin);

    while(scanf("%d%d",&N,&E)==2){



        if(N==0&&E==0) break;



        for(int i=0;i<=N;i++) makeSet(i);



        for(int i=0;i<E;i++){

            scanf("%d%d%d",&u,&v,&c);

            a[i].u=u;

            a[i].v=v;

            a[i].c=c;

        }



        sort(a,a+E,cmp);



        ll val=0;

        for(int i=0;i<E;i++){

            if(findSet(a[i].u)!=findSet(a[i].v)){

                Union(findSet(a[i].u),findSet(a[i].v));

                val+=a[i].c;

            }

        }

        cout<<val<<endl;

    }

    return 0;

}