- Описание
- Отправленные решения
8. Компоненты связности
- лёгкая
- dfs
Дан неориентированный невзвешенный граф, состоящий из $N$ вершин и $M$ ребер. Необходимо посчитать количество его компонент связности и вывести их.
Напомним:
Компонента связности в неориентированном графе - это подмножество вершин, таких что все вершины достижимы друг из друга.
Формат ввода
Во входном файле записано два числа N и M (0 $\lt$ N $\le$ 100000, 0 $\le$ M $\le$ 100000). В следующих M строках записаны по два числа i и j (1 $\le$ i, j $\le$ N), которые означают, что вершины i и j соединены ребром.
Формат вывода
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.
Пример 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
Нужно войти в систему / зарегистрироваться, чтобы отправить решение.