print997. День бульдозериста

printДень бульдозериста

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В некотором городе однажды выпал снег. Неожиданно выяснилось, что вся снегоуборочная техника находится на ремонте, и для расчистки улиц было решено привлечь тяжёлые гусеничные бульдозеры.
Задача осложняется тем, что асфальтовое покрытие улиц может выдержать только один проход такого бульдозера.
Город представляет из себя `N` площадей и `M` отрезков улиц между ними. Бульдозер может начинать расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может проезжать уже расчищенные площади). Если бульдозер оказывается на площади, все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным, бросает бульдозер и уходит.
Требуется определить минимально необходимое число бульдозеров.
Ввод
Входной файл содержит числа `N` и `M` за которыми идут `M` пар чисел `a_i` `b_i` –- номера площадей, соединенных `i`-й улицей (по улице, соединяющей площади `a_i` и `b_i`, можно проехать либо из `a_i` и `b_i`, либо из `b_i` в `a_i`). Две площади могут быть соединены больше чем одной улицей.
Вывод
В выходной файл должно быть выведено единственное число – наименьшее количество бульдозеров, необходимых для расчистки всех дорог и площадей города по указанным выше правилам.
Ограничения
`2\ ≤\ N\ ≤\ 40\ 000`, `1\ ≤\ M\ ≤\ 40\ 000`, `1\ ≤\ a_i,\ b_i\ ≤\ N`

Пример ввода 1

3 3
1 2 
2 3 
3 1

Пример вывода 1

1

Пример ввода 2

5 2 
1 2 
3 4

Пример вывода 2

3
Источник: И. Олейников, А. Кленин, ДВГУ, Весенний турнир, 2005
loading