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