Light OJ 1041 Road Construction

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
map<string,int>mp;
vector<int>graph[1000];
bool check[10009];
int cnt;
void dfs(int n)
{
    check[n]=1;
    for(int i=0;i<graph[n].size();i++)
    {
        int m=graph[n][i];
        if(check[m]==0)
        {
            dfs(m);
            cnt++;
        }
    }
}
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    int i,j,k,l,n,m,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cnt=0;
        cin>>m;
        memset(check,0,sizeof(check));
        int val=1;
        for(i=1;i<=m;i++)
        {
            string s1,s2;
            cin>>s1>>s2;
            if(!mp[s1])
            {
                mp[s1]=val;
                val++;
            }
            if(!mp[s2])
            {
                mp[s2]=val;
                val++;
            }
            int u,v,w;
            cin>>w;
            edge get;
            get.u=mp[s1];
            get.v=mp[s2];
            graph[get.u].push_back(get.v);
            graph[get.v].push_back(get.u);
            //cout<<get.u<<" "<<get.v<<endl;
            get.w=w;
            e.push_back(get);
        }
        dfs(1);
        //cout<<cnt<<" "<<val<<endl;
        cout<<"Case "<<k<<": ";
        if(abs(cnt-val)==2)
            cout<<mst(val-1)<<endl;
        else
            cout<<"Impossible"<<endl;
        mp.clear();
        e.clear();
        for(i=0;i<1000;i++)
        {
            graph[i].clear();
        }
    }
    return 0;
}