Здравствуйте, Кодт, Вы писали:

K>Две оставшиеся вершины можем себе позволить.
Нет, там по условию нужно вернуться в тот же город.

К>Вопрос, как сэкономить, объединив N-1 и (S/2)-1?

Тут главное — объединить компоненты связности в цикл, добавив, N ребер. В тех компонентах, в которых вершин с нечетной степенью нет, придется добавить два ребра одной из вершин, в тех, в которых вершины с нечетной степенью есть — взять любые две из них. Остальные вершины с нечетной степенью связывать можно как угодно. Таким образом количество дорог, которые нужно будет добавить равно S/2 + F, где F — количество компонент связности без вершин нечетной степени.