Light OJ 1041 - Road Construction

Problem link -  1041 - Road Construction

In this problem we are given m roads with this roads we have to create a mst. If there are n cities and if we can select n-1 edges from  all edges when running mst then we can say we have a solution as we got a tree :-)

For mapping the cities we can use STL map.

let us try to analyze some test cases

2

Rajshahi Khulna 4

Kushtia Bhola 1

here we can't select (4-1)=3 edges when running mst so the output should be impossible.

	#include<bits/stdc++.h>
	using namespace std;
	map<string,int>mp;
	int rep[110];
	void makeset(int n){
	for(int i=1;i<=n;i++){
	rep[i]=i;
	}
	}
	struct edge{
	int a, b, c;
	}arr[55];
	bool cmp(edge x,edge y){
	return x.c<y.c;
	}
	int finder(int x){
	if(rep[x]==x) return x;
	return rep[x]=finder(rep[x]);
	}
	int main(){
	int t,j;
	cin>>t;
	for(int k=1;k<=t;k++){
	int m;
	mp.clear();
	cin>>m;
	getchar();
	int y=0;
	j=1;
	for(int u=1;u<=m;u++){
	string a,b;
	int bb;
	cin>>a>>b>>bb;
	if(mp.find(a)==mp.end()){
	mp[a]=j;
	j++;
	}
	if(mp.find(b)==mp.end()){
	mp[b]=j;
	j++;
	}
	arr[y].a = mp[a];
	arr[y].b = mp[b];
	arr[y].c = bb;
	y++;
	}
	makeset(j);
	sort(arr,arr+y,cmp);
	int ed=0,sum=0;
	for(int q=0;q<y;q++){
	int x = finder(arr[q].a);
	int y = finder(arr[q].b);
	if(x!=y){
	rep[x]=y;
	ed++;
	sum = sum+ arr[q].c;
	}
	}
	if(ed != j-2){
	printf("Case %d: Impossible\n",k);
	}
	else{
	printf("Case %d: %d\n",k,sum);
	}
	}
	return 0 ;
	}

view raw 1041 - Road Construction.cpp hosted with ❤ by GitHub