UVA 11857 - Driving Range(cpp file)

Problem Type : Graph(Minimum Spanning Tree)




#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
long par[MAX],n,m,color[MAX];

struct node
{
    long node1;
    long node2;
    long  cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=0; 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,k,ux,uy;
    while(scanf("%ld %ld",&n,&m)==2)
    {
        if(n==0 && m==0)
        {
            break;
        }
        //printf("%d\n",m);
        for(i=0;i<m;i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }
        make_set();
        sort(arr,arr+m,comp);
        long s=0,cou=0;

        for(i=0; i<m; i++)
        {
            ux=find_set(arr[i].node1);
            uy=find_set(arr[i].node2);
            if(ux!=uy)
            {
                cou++;
                par[ux]=uy;
                s=arr[i].cost;
            }
            if(cou==n)
                break;

        }
        long vx;
        cou=0;
        ux=find_set(0);
        for(i=1; i<n; i++)
        {
            vx=find_set(i);
            if(ux!=vx)
            {
                printf("IMPOSSIBLE\n");
                cou=1;
                break;
            }

        }
        if(cou==0)
        {
            printf("%ld\n",s);
        }

    }
}