Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче:
Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях.
Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки.
Или, на языке алгоритмов, надо построить Эйлеров путь. И по теореме Эйлера (которую он только сформулировал, но не доказал) нужно, чтобы не больше двух вершин имели нечётную степень. Причём путь будет из одной такой вершины в другую.
Если развить идею дальше, то получим, что надо K / 2 (но не меньше 1) путей, где K - число вершин с нечётной степенью. Вот мы и подошли к принципиальному решению задачи. Последняя сложность - граф из задачи может быть несвязный, поэтому все подсчёты надо делать для каждой компоненты связности.
Определим нужные нам библиотеки, их здесь очень мало:
Раз мы знаем, что надо хранить граф и выделять в нём компоненты связности, заведём список инцидентности и напишем обход в глубину, который сразу красит вершины в заданный цвет. Так мы сможем отличить вершины одной компоненты связности от другой:
В основной функции первым делом считаем входные данные и сложим номера вершин в списки инцидентности нашего графа:
Выделим компоненты связности, запустив обход в глубину от всех вершин, которые ещё не было посещены до этого:
Теперь для выделенной компоненты связности можно посчитать нужные нам статистики:
- количество вершин с нечётной степенью,
- количество вершин в компоненте связности (есть коварный тест, когда в компоненте лишь одна вершина, тогда и ковбоя задействовать не надо).
Пройдём по всем вершинам и в r прибавим количество ковбоев, необходимых для этой компоненты связности:
Дальше осталось лишь вывести ответ:
Мы написали очень простое решение задачи. Его можно улучшить, если перенести подсчёт статистик в обход в глубину. Можете попробовать сделать это самостоятельно.
В нашем случае решение работает за O(N^2 + M).
Предыдущий выпуск: Задача 614. Скобки - 3
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
