Second best mst (using Kruskal)

Sometimes we are asked to find Second best mst in some problems. We can do this with brute force.
At first we will find the mst and all the edges of mst. From all the edges of mst we will remove every edge once and and will create a new mst. In this way the minimum of all newly created mst is the Second best mst

mst:

yellow edges are edges of mst

sum of all weights is 110.














Second best mst:

yellow edges are edges of second best mst

sum of all weights is 121.












Implementation:

	#include<bits/stdc++.h>
	using namespace std;
	int rep[100005];
	vector<int>va;
	int edg;
	int a[100005];
	struct edge{
	int a, b , c;
	}arr[100005];
	bool cmp( edge x, edge y ){
	return x.c < y.c;
	}
	void makeset(int n){
	for(int i=1;i<=n;i++) rep[i]=i;
	}
	int findr( int x ){
	if( rep[x] == x ) return x;
	return rep[x] = findr( rep[x] );
	}
	int unio(int i,int sum){
	int x,y;
	x = findr( arr[i].a );
	y = findr( arr[i].b );
	if( x != y ){
	rep[x] = y;
	va.push_back(i);
	sum += arr[i].c;
	}
	return sum;
	}
	int unio2(int i,int sum){
	int x,y;
	x = findr( arr[i].a );
	y = findr( arr[i].b );
	if( x != y ){
	rep[x] = y;
	sum += arr[i].c;
	edg++;
	}
	return sum;
	}
	int main(){
	int n , m;
	cin >> n >> m;
	makeset(n);
	for( int i = 0; i < m; i++ ){
	int a, b, c ;
	cin >> a >> b >> c;
	arr[i].a = a;
	arr[i].b = b;
	arr[i].c = c;
	}
	sort( arr, arr+m , cmp );
	int sum=0;
	for(int i=0;i<m;i++){
	sum=unio(i,sum);
	}
	cout <<"MST: "<< sum << "\n"; //cost
	int sec_best_mst=INT_MAX/3;
	cout<<"All other spanning trees:\n";
	sum=0;
	int j;
	for(j=0;j<va.size();j++){
	makeset(n);
	edg=0;
	for(int i=0;i<m;i++){
	if(i==va[j]) continue;
	sum=unio2(i,sum);
	}
	if(edg!=n-1){
	sum=0;
	continue;
	}
	cout<<sum<<"\n" ;
	if(sec_best_mst>sum) sec_best_mst = sum;
	sum=0;
	}
	cout<<"SEC BEST MST: "<<sec_best_mst<<"\n";
	}

view raw second best mst.cpp hosted with ❤ by GitHub