up79's blog

cananyone help me in this question?
By up79, history, 4 years ago, In English

https://codeforces.net/contest/744/problem/A

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

complete all connected components, then unite all capitalless components to largest component which has government home

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There are K nodes corresponding to governments and none of them are initially connected by any path and you should never connect any of them by some path. So basically there are some connected components initially. You find each of those connected components by dfs. You will not connect any two nodes of different connected components because of the condition in the first line. For each connected component maximum number of edges that you can put is n*(n-1)/2 where n is the number of nodes in that connected component. Some edges were already in the connected component so you can just subtract their amount to get the number of "new" edges that you can put.

Now some connected components might not contain any government node. You can actually merge these connected components into one large connected component and this way you may put more edges into the graph. And also you can merge all of them with a connected component that already has a government node. This way you can form one large connected component and you want that to be largest (greedy thinking). So pick the largest connected component with a government node and merge all of the "connected components without government node" with this component to make one large component. And now you can calculate total number of edges you can insert into graph.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    7 3 3 these are goverment roads? 1 5 6 these are edges 1 2 1 3 6 7 can you please tell me how the answer is four?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://imgur.com/oxPzp9K — you can see that graph here. Now you have 4 components and 1 of those components is only with node 4 and that does not contain any government nodes (1,5 or 6). So we can merge this with another connected component, either with (1,2,3) or with (6,7). We want the component to be as large as possible so we merge it with (1,2,3) and we have 3 components (1,2,3,4) , (6,7), (5). And now there are no more merging possible, else you will end up creating path between 2 government nodes. Now you just insert edges. A connected component of n nodes can have n*(n-1)/2 edges at max. So

      (1,2,3,4) — 6 edges

      (6,7) — 1 edge

      (5) — 0 edge

      But some of these edges were already given to you and the number of edges that were already given to you is given as input that is "m". So your total possible edge = 6 + 1 + 0 = 7. Given edges were m = 3. So you can add 4 "new" edges.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please post the merging graph thanks in advance

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          https://imgur.com/a/LbJmtIE — I used the word "merging" because it's comfortable for me. It's just that if you connect any two node belonging to 2 different connected components, then they become 1 big connected component. Here I added 1-4, but that was not essential, 2-4 or 3-4 is completely fine.

          → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just did read the editorial. How can one come up with that solution given that problem statement? The statement says nothing about countries, and/or the way how cities belong to countries.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      yes! i also have the same question. the question statement is improper

      → Reply