Kruskals MST example

uva_DarkRoads_11631.cpp

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
#define MAXN 200003
using namespace std;
struct edge
{
    long u,v,w;
    bool operator < ( const edge& p ) const
    {
        return w < p.w;
    }
};

long pr[MAXN];
int find(long r)
{
	if(pr[r]==r)
		return r;
	else
		return pr[r]=find(pr[r]);
}

vector<edge>e;
int mst(long n)
{
    sort(e.begin(),e.end());
    long count=0,s=0;
    for(long i=0;i<(long)e.size();i++)
    {
        long u=find(e[i].u);
        long v=find(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            count++;
            s+=e[i].w;
            
            if(count==n-1)
		break;
        }
    }
    return s;
}

int main()
{
    long n,m,sum;
    while(scanf("%ld%ld",&n,&m)==2)
    {
      if(!n && !m)
        break;
      
      memset(pr,0,sizeof(pr));
      e.clear();
      sum=0;
      for(long i=0;i<m;i++)
      {
        long u,v,w;
        pr[i]=i;
        scanf("%ld%ld%ld",&u,&v,&w);
        edge get;
        get.u=u; get.v=v; get.w=w;
        sum=sum+w;
        e.push_back(get);
      }
      
      long save=sum-mst(n);
      printf("%ld\n",save);
    }
    return 0;
}