Листья дерева мостов
3000 мс · 256 МБ · всё или ничего
Постройте дерево мостов и посчитайте количество его листьев — компонент, из которых выходит ровно один мост.
Именно это число отвечает на два вопроса сразу: сколько серверов нужно в отказоустойчивом множестве и сколько рёбер надо добавить до рёберной двусвязности (там ответ — половина, округлённая вверх).
Формат ввода
В первой строке и (, ). В каждой из следующих строк — концы ребра. Граф может быть несвязным, кратные рёбра допустимы, петель нет.
Формат вывода
Выведите количество листьев дерева мостов.
Примеры
ввод
4 3 1 2 2 3 3 4
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.