themechanicalcoder's blog

Need help in a problem

By themechanicalcoder, history, 6 years ago, In English

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 code was fine on the test case but I am getting the verdict wrong answer can someone please help

my solution

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understood what you are trying to say but how will I implement that

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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);
}
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What if is_valid is false what will be the answer in that case ?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply