Ну очень распространённый метод для графов...
Ну очень распространённый метод для графов...
Виталий Гольдштейн на Зимней Школе рассказывал о графах, о белых, чёрных и серых вершинах, о решении многих задачек на графы методом поиска в глубину. А на подведении итогов начал рассказывать о трудной жизни программиста и поэтому забыл всем на Зимней Школе в Харькове 2011 задать ещё одну задачку, которую также можно решить указанным методом. Естественно, Виталий, не мог забыть о ней и попросил нас всё-таки предложить всем эту задачку, ибо, как настоящий мастер-лектор он не должен упустить возможности поставить какую-то, пусть и простую задачку, при любом общении с аудиторией, даже если это общение происходит дистанционно.
Итак, ещё одна его простая задачка, решаемая методом поиска в глубину, звучит так: “Вам задан неориентированный граф с N вершинами и M ребрами (1 ≤ N ≤ 20000, 0 ≤ M ≤ 200000). В графе отсутствуют петли и кратные ребра. Определите компоненты связности заданного графа.”
Входные данные
Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержит описание ребра – два целых числа из диапазона от 1 до N – номера концов ребра.
Выходные данные
В единственной строке выведите число L – количество компонент связности заданного графа.
Пример
4 2 1 2 3 4
2