Компоненты связности
(Время: 2 сек. Память: 16 Мб Сложность: 47%)
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N и M – число вершин и ребер в графе (1 ≤ N, M ≤ 105). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй – сами вершины в произвольном порядке.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6 4
3 1
1 2
5 4
2 3 | 3
3
1 2 3
2
4 5
1
6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|