Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
 

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

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

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

В некотором городе однажды выпал снег. Неожиданно выяснилось, что вся снегоуборочная техника находится на ремонте, и для расчистки улиц было решено привлечь тяжёлые гусеничные бульдозеры.
Задача осложняется тем, что асфальтовое покрытие улиц может выдержать только один проход такого бульдозера.
Город представляет из себя N площадей и M отрезков улиц между ними. Бульдозер может начинать расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может проезжать уже расчищенные площади). Если бульдозер оказывается на площади, все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным, бросает бульдозер и уходит.
Требуется определить минимально необходимое число бульдозеров.
Ввод
Входной файл содержит числа N и M за которыми идут M пар чисел ai bi –- номера площадей, соединенных i-й улицей (по улице, соединяющей площади ai и bi, можно проехать либо из ai и bi, либо из bi в ai). Две площади могут быть соединены больше чем одной улицей.
Вывод
В выходной файл должно быть выведено единственное число – наименьшее количество бульдозеров, необходимых для расчистки всех дорог и площадей города по указанным выше правилам.
Ограничения
2 , 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