10600 - ACM Contest and Blackout

#include<stdio.h>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAX 10000

using namespace std;

struct node
{
    int u,v,cost;

} arr[MAX+3];

int par[110];
vector<int>vec1;

bool cmp(node lhs,node rhs)
{
    return lhs.cost<rhs.cost;
}


int khoj_rep(int r)
{
    if(par[r]==r)
    {
        return r;
    }
    else
    {
        return par[r]=khoj_rep(par[r]);
    }
}


int main()
{
    int test,node,edge,i,j,k,u1,v1,counter,sum,sum1,minimum,value,a,b;
    cin>>test;

    while(test--)
    {
        cin>>node>>edge;

        for(i=0; i<edge; i++)
        {
            cin>>arr[i].u>>arr[i].v>>arr[i].cost;
        }

        sort(arr,arr+edge,cmp);

        for(j=1; j<=node; j++)
        {
            par[j]=j;
        }

        counter=0;

        sum=0;
        for(i=0; i<edge; i++)
        {
            u1=khoj_rep(arr[i].u);
            v1=khoj_rep(arr[i].v);
            if(u1!=v1)
            {
                par[u1]=v1;
                counter++;
                vec1.push_back(i);
                sum+=arr[i].cost;
                if(counter==node-1)
                {
                    break;
                }
            }
        }

        memset(par,0,sizeof(par));
        minimum=30000;

        a=0;
        for(i=0; i<counter; i++)
        {
            for(k=1; k<=node; k++)
            {
                par[k]=k;
            }

            sum1=0;
            for(j=0; j<edge; j++)
            {
                if(j==vec1[i])
                {
                    continue;
                }
                u1=khoj_rep(arr[j].u);
                v1=khoj_rep(arr[j].v);
                if(u1!=v1)
                {
                    par[u1]=v1;
                    sum1+=arr[j].cost;
                }
            }

            if(sum1>=sum)
            {
                value = abs(sum1-sum);
                if(value<minimum)
                {
                    minimum=value;
                    b=sum1;
                    a=1;
                }
            }
            memset(par,0,sizeof(par));
        }
        cout<<sum;
        if(a==1)
        {
            cout<<" "<<b<<endl;
        }
        else
        {
            cout<<" "<<sum<<endl;
        }

        memset(par,0,sizeof(par));
        vec1.clear();
    }
    return 0;
}