Shadi_Bahaa's blog

By Shadi_Bahaa, history, 7 weeks ago, In English

Hi!

I tried to solve this problem https://onlinejudge.org/external/106/10600.pdf?fbclid=IwAR2tGCAnxFqS61oAKAMBdN5qQ2zej1Ta1yjj8NN-teRJ8CeA3vNAOsws97U using Kruskal algorithm to find the two minimum spanning trees. The first MST is always correct. Although the logic of the second I implemented is the same, the second MST cost is not correct at all! Kindly Can someone tell me what is wrong with my code? This is my code: https://ideone.com/spXa9w

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can you share your approach to how you find the second-best MST?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Each time I neglect one of the edges which form the first minimum spanning tree. As a result, the remaining ones when form a tree, if possible, their total cost won't exceed the first one.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Think about it -- this is a right thought process, however you want to remove the biggest weight edge to a leaf node. Those are the only nodes that you can safely remove without making more than one connected component.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The strictly second smallest MST require a different algorithm than running 2 kruskal and is much more complicated than that. One way to do it is connect all edges of MST, then delete any of them and add any edge. If after that edge we get a self loop or there is a point not connected, then we reject the answer. We loop through all to find the second minimum.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that is what I implemented in my code. I deactivate a different edge each time from the first tree then I begin to test the other edges. If I am wrong, I hope to clarify more.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The way your deactivating the edge is wrong. What you are doing is deleting an edge every time, which make one of its endpoints never reachable hence you get no answer. What you should do is get the MST, and loop through all other edges to find the minimum increment, and add those edge into MST. Then it will form a loop in the tree. Find the loop using either LCA or other methods, and deleted the largest edge in it. Then you find the new cost.