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.

minimum spanning tree (Kruskal's algorithm) Implementation

There is an awesome kruskal algorithm tutorial  in - shafaetsplanet

here I will try to implement the algorithm in my way

a normal undirected graph

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.

Light OJ 1040 - Donation

Problem link - 1040 - Donation

Its a very basic mst problem.

let us try to analyze some test case

2

27 26

1 52