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

×

744A (Codeforces) Hongcow Builds A Nation help!

I'm not able to understand the editorial of this question on graph (Codeforces)! Can someone please explain what is the approach for solving it?

asked 10 Feb '18, 22:24

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 11 Feb '18, 00:00


this question is about finding the connected component . In a fully connected graph we have maximum edges so one govt house cannot be connected to other so connect all the nodes of this component to one another and the cities which are not connected to any govt connect them to component which have maximum nodes Accepted solution

link

answered 11 Feb '18, 08:12

anno's gravatar image

4★anno
266211
accept rate: 12%

I understood the following things:

  1. Gov nodes can't have a path between them
  2. Gov nodes can be connected to nodes that aren't connected to any other gov nodes
  3. Components having no gov node can be merged forming complete graph( n(n-1)/2 edges )

@anno I couldn't understand component having maximum nodes part?

link

answered 11 Feb '18, 10:05

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

1

see there may be some node or components which are not connected to any govt node so we will connect them to the component having maximum nodes so that there will be more number of edges take an example there is component with 5 node and one with 6 nodes these both have one govt node and we also have node which is not connected to any govt node if we will connect it with 5 number of edges that will increase will be 5 (we will connect it to all nodes of that component ) but if we will connect it to component having 6 nodes number of edges that will increase will be 6

(11 Feb '18, 18:33) anno4★
1

so make a component of all the nodes which are not connected to any govt node and connect that to component having maximum nodes so that we can have more increase in number of edges

(11 Feb '18, 18:34) anno4★

thanks :) it helped

(11 Feb '18, 22:55) dushyant79175★
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:

×15,639
×2,718
×1,217
×672
×2

question asked: 10 Feb '18, 22:24

question was seen: 287 times

last updated: 11 Feb '18, 22:55