Maximum Distance

codeforces

question link: https://codeforces.com/contest/1081/problem/D

I saw the editorial, i don't get the part where they are applying the DSU and how they are getting the answer from DSU.  Can anyone help..?

P.S.: i know krushkal's and DSU..!! :)

Samrat
Samrat De
Samrat

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

preda2or
preda2or 12:38, Jan 20
Shubham Kumar Gupta

Here is how you approach ....
Sort all the edges ,now connect the edges in increasing order of their weights...
Make sure whenever there is a special node ...while joining make the special node the parent node ..so that you node that there is a special node in this set...

Joining process
If both the roots are special ,then this edge is important...means you have to use it to visit all the special nodes...
If only one is special ...then this edge is not important ....it could be a case that this connection is not needed...
If none are special .then too the edge is not important ..

So you just have to check the last important edge and keep joining the edges irrespective of they are important or not..




Please make sure the answer is not too short
1 Upvotes
Comments
No Comments yet