UVA 1174 - IP-TV(cpp file)

Problem Type :Graph( Minimum Spanning Tree)




#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#define MAX 50002
using namespace std;
long int par[MAX],n,m,cou;
map<string,long int>mymap;
struct name
{
    long int node1;
    long int node2;
    long int cost;
};
name arr[MAX];
void make_set()
{
    long int i;
    for(i=0; i<n; i++)
    {
        par[i]=i;
    }

}
int find_set(long int n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
bool comp(name x,name y)
{
    return x.cost<y.cost;
}
long int  Union(long int x,long int y)
{
    long   int ux,uy;
    ux=find_set(x);
    uy=find_set(y);
    if(ux==uy)
    {
        return 0;
    }
    else
    {
        cou++;
        par[ux]=uy;
        return 1;
    }
}
int main()
{
    long  int test,i,j,c1,node,k,cou,sum,cas=0,ux,uy,x,y;
    string n1,n2;
    scanf("%ld",&test);
    getchar();
    getchar();
    while(test--)
    {
        node=0;
        i=0;
        scanf("%ld %ld",&n,&m);
        getchar();
        k=m ;
        for(n=0; n<m; n++)
        {
            cin >>n1>>n2>>c1;
            if(mymap.find(n1)==mymap.end())
            {
                mymap[n1]=node;
                node=node+1;
            }
            if(mymap.find(n2)==mymap.end())
            {
                mymap[n2]=node;
                node=node+1;
            }

            x =mymap[n1];
            y =mymap[n2];
            arr[n].node1=x;
            arr[n].node2=y;
            arr[n].cost=c1;
        }
        sort(arr,arr+m,comp);
        make_set();
        cou=0;
        sum=0;
        for(i=0; i<m; i++)
        {
            ux=arr[i].node1;
            uy=arr[i].node2;
            x=Union(ux,uy);
            if(x!=0)
            {
                sum+=arr[i].cost;
            }
            if(cou==n)
                break;
        }
        if(cas!=0)
            printf("\n");
        cas++;

        printf("%ld\n",sum);

        mymap.clear();
    }
    return 0;
}