ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64186
Тема:    [ Обход графа в ширину ]
Сложность: 2
Классы: 8
В корзину
Прислать комментарий

Условие

"Компоненты связности"

В неориентированном графе посчитать количество компонент связности.
В графе могут быть петли и кратные ребра.

Входные данные.
Во входном файле INPUT.TXT записаны сначала два числа N и M,
задающие соответственно количество вершин и количество ребер
(1<=N<=100, 0<=M<=10000), а затем перечисляются ребра. Каждое ребро
задается номерами вершин, которые оно соединяет.

Выходные данные.
В выходной файл OUTPUT.TXT выведите одно число - количество компонент
связности.

Пример входного файла	
3 4
1 1 1 2 1 3 2 3

Пример выходного файла
1

Пример входного файла	
5 3
1 1 1 2 2 1

Пример выходного файла
4

Пример входного файла	
5 0

Пример выходного файла
5

Подсказка

Решение - тоже волна, помечающая компоненту связности. Идея не так проста, как может казаться.


Решение

Скачать архив тестов

Источники и прецеденты использования

Курс
предмет информатика
Название Основы программирования на языке Паскаль
Класс 8
Автор Матюхин Виктор Александрович
Место проведения Московская гимназия на Юго-Западе N1543
задача
Номер 164

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .