< Back to forum

Maximum Distance

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..!! :)

codeforces

Asked by: Samrat_De on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

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..

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.