×

# 744A (Codeforces) Hongcow Builds A Nation help!

 0 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 71●6 accept rate: 0%

 0 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 answered 11 Feb '18, 08:12 4★anno 266●2●11 accept rate: 12%
 0 I understood the following things: Gov nodes can't have a path between them Gov nodes can be connected to nodes that aren't connected to any other gov nodes 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? answered 11 Feb '18, 10:05 71●6 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)
 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:

×15,638
×2,714
×1,217
×672
×2

question asked: 10 Feb '18, 22:24

question was seen: 286 times

last updated: 11 Feb '18, 22:55