How can I find second best Minimum Spanning Tree using DSU?
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
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.