satmangod100's blog

By satmangod100, history, 7 weeks ago, In English

1609D — Social Network Note that the conditions form a collection of disjoint sets. Consider two situations:

  • The next condition connects two previously unconnected sets: then we will simply unite.
  • The next condition connects two previously connected sets: this case allows us to "postpone" an edge to use it as we like.

in this problem how we can conclude the second observation .. if it is previously connected.. unable to understand.

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

At each ith turn, we can add introduce two people (two components) and the ith condition requires ai should know bi and all conditions before should be fulfilled. So if the ith condition is already met (they belong to the same component) then we can just introduce any two people with each other (two-person of the largest and the second-largest component to maximize the answer).

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks frozen kandy . so the problem says that if all the condition are true we can connect some other components .

    I thought if a1 is not connected to some a2 till the ith than it should not be connect at all till that operation..

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, so if we have c such cases where the two people already know each other. Then we can just introduce the people from c largest component to make one big component.