UVA 11710 - Expensive subway(cpp file)

Problem Type : Graph (Minimum Spanning Tree)



#include<bits/stdc++.h>
#define MAX 100000
using namespace std;
long par[MAX],n,m;
map<string ,long >mymap;
string n1,n2,n3;
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;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
bool comp(node x,node y)
{
    return x.cost < y.cost;
}
int main()
{
    long i,j,k,l,node,x,y,c,ux,uy,px,cou,sum;
    while(scanf("%ld%ld",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        getchar();
        for(i=0; i<n; i++)
        {
            cin >> n1;
            mymap[n1]=i;
        }
        for(i=0; i<m; i++)
        {
            cin>> n2 >>n3 >> c;
            x=mymap[n2];
            y=mymap[n3];
            arr[i].node1=x;
            arr[i].node2=y;
            arr[i].cost=c;
        }
        cin >> n1;
        x=mymap[n1];
        make_set();
        sort(arr,arr+m,comp);
        cou=0;
        sum=0;
        for(i=0; i<m; i++)
        {
            ux= find_set(arr[i].node1);
            uy= find_set(arr[i].node2);
            if(ux!=uy)
            {
                sum+=arr[i].cost;
                par[ux]=uy;
                cou++;

            }
            if(cou==n)
                break;
        }
        px= find_set(x);
        cou=0;
        for(i=0; i<n; i++)
        {
            if(i==x)
                continue;
            else
            {
                ux=find_set(i);
                if(ux!=px)
                {
                    cou=1;
                }

            }
        }
        if(cou==1)
            printf("Impossible\n");
        else
        {
            printf("%ld\n",sum);
        }
        mymap.clear();

    }

}