### themechanicalcoder's blog

By themechanicalcoder, history, 3 months ago, ,

I was solving the problem Uva 10600 in which we have to find the minimum and second minimum spanning tree I found the minimum spanning tree using kruskal's algorithm and stored the edges in a vector mst then to find the second minimum spanning tree I did this

second_tot_wt=INF for edge in mst : second_tot_wt=min(second_tot_wt,total weight of the minimum spanning tree ignoring this edge)

my solution

 » 3 months ago, # | ← Rev. 2 →   +13 Hi! When you try to find the second spanning tree you need to check that after ignoring some edge, every node is in the same component, for example: 4 nodes and 4 edges from 1 to 2 weight 1 from 2 to 3 weight 1 from 1 to 3 weight 3 from 3 to 4 weight 1 when you run kruskal you found that the mst uses edges 1, 2, and 4, then you try to remove each edge in the mst, but if you remove edge 4 you get an answer equal to 2 and it is wrong, because you don't connect node 4 with nodes 1, 2, and 3.
•  » » 3 months ago, # ^ |   0 I understood what you are trying to say but how will I implement that
•  » » » 3 months ago, # ^ |   +10 After you run kruskal, iterate over each node and check that the parent is equal for every node, something like that: int cur = kruskal(mst[i]); bool is_valid = true; for( int i = 0; i < n; ++i ) { if( find_(i) != find_(0) ) { is_valid = false; break; } } if( is_valid ) { swt=min(swt, cur); } 
•  » » » » 3 months ago, # ^ |   0 What if is_valid is false what will be the answer in that case ?
•  » » » » » 3 months ago, # ^ |   0 When is_valid is equal to false means that after removing edge mst[i] doesn't exist a valid mst. So, the only way to get false in every iteration is when the original graph is a tree, because you don't have extra edges. I didn't read the statement, so you should check what happens if the original graph is a tree, or even if the original graph doesn't connect every node in the same component
•  » » 3 months ago, # ^ |   0 Can you provide some idea about how i can implement it