Solution of Light OJ 1041 - Road Construction

/* Bismillahir Rahmanir Rahim Solution using (MST)Kruskal's algorithm. */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; map<string, string>pr; set<string>st; set<string>::iterator it; int ct, n; struct edge{ string u, v; int w; }one[55]; string find(string p){ while(pr[p]!=p){ p=pr[p]; } return p; } bool comp(edge f, edge s){ return f.w<s.w; } int mst(int st){ int cnt=0, sm=0; string xx, yy; fi(0, n-1){ xx=find(one[i].u); yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].w; } if(cnt==ct-1)return sm; } return -1; } int main(){ int t, cs=1, w, ans; string u, v; cin>>t; while(t--){ cin>>n; fi(0, n-1){ cin>>u>>v>>w; st.insert(u); st.insert(v); one[i].u=u; one[i].v=v; one[i].w=w; } for(it=st.begin(); it!=st.end(); it++){ pr[*it]=*it; } ct=st.size(); sort(one, one+n, comp); ans=mst(0); cout<<"Case "<<cs++<<": "; if(ans!=-1)cout<<ans<<endl; else cout<<"Impossible"<<endl; st.clear(); pr.clear(); } return 0; }