UVA 10034 - Freckles(cpp file)

Problem Type : Graph (Minimum Spanning Tree)


#include<stdio.h>
#include<math.h>
#include<algorithm>
#define MAX 5000
using namespace std;
int n,par[MAX];
struct node
{
    int n1;
    int n2;
    double cost;

};
node arr[MAX];
struct cor
{
    double px;
    double py;
};
cor arra[MAX];
bool comp(node x ,node y)
{
    return x.cost<y.cost;
}

void make_set()
{
    int i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }
}
int find_set(int n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
int main()
{

    double mat[MAX],u,v,a,b,sum;
    int test,i,j,k,len,c,cas=0,ux,uy;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%lf %lf",&arra[i].px,&arra[i].py);
        }
        make_set();
        c=0;
        for(i=0; i<n-1; i++)
        {
            for(j=i+1; j<n; j++)
            {
                a=pow((arra[i].px-arra[j].px),2);
                b=pow((arra[i].py-arra[j].py),2);
                arr[c].n1=i;
                arr[c].n2=j;
                arr[c].cost=sqrt(a+b);
                c++;
            }
        }
        sort(arr,arr+c,comp);
        int cnt=0;
        sum=0;
        for(i=0; i<c; i++)
        {
            ux=find_set(arr[i].n1);
            uy=find_set(arr[i].n2);
            if(ux!=uy)
            {
               par[ux]=uy;
                sum+=arr[i].cost;
                cnt++;
                if(cnt==n)
                    break;

            }

        }
        if(cas!=0)
            printf("\n");
        cas++;
        printf("%.2lf\n",sum);

    }

}