Блог пользователя Ibodullo_Yorov

Автор Ibodullo_Yorov, история, 8 лет назад, По-русски

Всем доброго времени суток !
Можете пожайлуста объяснить эту задачу!
Заранее спасибо !

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Большая подсказка — так как граф связный, и в нем N вершин и N ребер, то это цикл, к которому подвешено несколько деревьев.

Думаю, это поможет в дальнейших рассуждениях. Нужно лишь рассмотреть несколько случаев.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Спасибо! Я тоже это заметил , но всё таки решить не смог. Только на 30 баллов смог.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Ну, как бы для решения на 30 и даже 50 баллов совсем не обязательно что-то замечать, а достаточно просто написать поиск в ширину из каждой вершины.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Как же горело, когда у меня было 250 за полтора часа и я таки не заметил, что там N ребер. Контест я закончил с 250 баллами. :(