- Описание
- Отправленные решения
8. Компоненты связности
Дан неориентированный невзвешенный граф, состоящий из вершин и ребер. Необходимо посчитать количество его компонент связности и вывести их.
Напомним:
Компонента связности в неориентированном графе - это подмножество вершин, таких что все вершины достижимы друг из друга.
Формат ввода
Во входном файле записано два числа N и M (0 N 100000, 0 M 100000). В следующих M строках записаны по два числа i и j (1 i, j N), которые означают, что вершины i и j соединены ребром.
Формат вывода
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
Ввод
6 4
3 1
1 2
5 4
2 3
Вывод
3
3
1 2 3
2
4 5
1
6
Пример 2
Ввод
6 4
4 2
1 4
6 4
3 6
Вывод
2
5
1 2 3 4 6
1
5