×

Second Best MST

 0 How can I find second best Minimum Spanning Tree using DSU? asked 19 May '18, 12:19 10●2 accept rate: 0%

 0 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 answered 19 May '18, 15:57 3●2 accept rate: 0% 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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