You are not logged in. Please login at www.codechef.com to post your questions!

×

Second Best MST

How can I find second best Minimum Spanning Tree using DSU?

asked 19 May '18, 12:19

saurabh18213's gravatar image

5★saurabh18213
102
accept rate: 0%

converted to question 19 May '18, 13:51


If you have the MSt, let's say that the Mst's edges are in the array e[N] and we know that e[i].w <= e[i+1].w we have m — n + 1 queries which are like what is the longest edge's weight from u to v in the mst (the queries are the edges which are not in mst) now let's say that at first all vertices are in their own sets and we will add edges one by one and we will merge the two sets which are located at the endpoint of the edges (move the smaller one to the bigger one) and we will check the queries of the smaller one to see if there is any queries that goes from the smaller to the bigger one the answer of the query is this edge's weight the complexity is O(qlogn + nlogn).

understood and presented

link

answered 19 May '18, 15:57

rishabhjha708's gravatar image

2★rishabhjha708
32
accept rate: 0%

edited 19 May '18, 15:59

I have already seen this comment on http://codeforces.com/blog/entry/19674?#comment-244772. But I could'nt understand what is meant by checking the queries of smaller set.

(19 May '18, 19:38) saurabh182135★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×185
×117
×72

question asked: 19 May '18, 12:19

question was seen: 301 times

last updated: 19 May '18, 19:38