UVA 908 - Re-connecting Computer Sites(cpp file)

Problem Type : Minimum Spanning Tree




#include<stdio.h>
#include<algorithm>
#define MAX 1000001
using namespace std;
long par [MAX],n,m,k;
struct node
{
    long node1;
    long node2;
    long cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
bool comp(node x,node y)
{
    return x.cost <y.cost;
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
int main()
{
    long i,j,cas=0,cou,sum,ux,uy,sum1;
    while(scanf("%ld",&n)==1)
    {
        make_set();
         for(i=1; i<n; i++)
         {
             scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);

         }
         arr[0].node1=0;
         arr[0].node2=0;
         arr[0].cost=0;
         sum=0;
         cou=0;
         sort(arr,arr+n,comp);
         for(i=1; i<n; i++)
         {
             ux=find_set(arr[i].node1);
             uy=find_set(arr[i].node2);
             if(ux!=uy)
             {
                 par[ux]=uy;
                 cou++;
                 sum+=arr[i].cost;
             }
             if(cou==n)
                 break;
         }

        scanf("%ld",&k);

        arr[0].node1=0;
        arr[0].node2=0;
        arr[0].cost=0;
        for(i=1; i<=k; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        scanf("%ld",&m);
        for(i=k+1; i<=k+m; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        long s=k+m+1;
        make_set();
        cou =0;
        sum1=0;
        sort(arr,arr+s,comp);
        for(i=1; i<=s;i++)
        {
            ux=find_set(arr[i].node1);
            uy = find_set(arr[i].node2);
            if(ux!=uy)
            {
                par[ux]=uy;
                cou++;
                sum1+=arr[i].cost;
            }
            if(cou==n)
                break;
        }
        if(cas!=0)
            printf("\n");
        cas++;
        printf("%ld\n%ld\n",sum,sum1);
        }

}