744A (Codeforces) Hongcow Builds A Nation help!

editorial
, , , ,
1

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?

2

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

3

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?

4

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

1 Like
5

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

1 Like
6

thanks :slight_smile: it helped