← вернуться к уроку · Продвинутый уровень: проверь себя
C. Сколько компонент
3000 мс · 256 МБ · всё или ничего
Неориентированный граф задан списком рёбер. Посчитайте количество компонент связности.
Компонента связности — максимальный набор вершин, попарно связанных путями. Считаются они одним циклом: запускаем обход из каждой ещё непосещённой вершины, и сколько раз запустили — столько и компонент.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Возможны петли и кратные рёбра.
Формат вывода
Одно число — количество компонент связности.
Примеры
ввод
5 3 1 2 2 3 4 5
вывод
2
ввод
100000 0
вывод
100000
Войдите, чтобы отправлять решения.