EduBrick
← вернуться к уроку · Продвинутый уровень: проверь себя

C. Сколько компонент

3000 мс · 256 МБ · всё или ничего

Неориентированный граф задан списком рёбер. Посчитайте количество компонент связности.

Компонента связности — максимальный набор вершин, попарно связанных путями. Считаются они одним циклом: запускаем обход из каждой ещё непосещённой вершины, и сколько раз запустили — столько и компонент.

Формат ввода

Первая строка содержит числа nn (1n1051 \le n \le 10^5) и mm (0m21050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Возможны петли и кратные рёбра.

Формат вывода

Одно число — количество компонент связности.

Примеры

ввод
5 3
1 2
2 3
4 5
вывод
2
ввод
100000 0
вывод
100000
Войдите, чтобы отправлять решения.
← Вернуться к уроку