Посчитать количество компонент связности графа

@plan_z · Регистрация: 27.12.2015

Студворк — интернет-сервис помощи студентам

Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их.

Входные данные
Во входном файле записано два числа N и M (0 < N ≤ 100000, 0 ≤ M ≤ 100000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.

Выходные данные
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.

Примеры
входные данные
6 4
3 1
1 2
5 4
2 3
выходные данные
3
3
1 2 3
2
4 5
1
6

@dondublon · 13.07.2016, 09:45

В чём проблема?
Делается заливкой.
Сначала считаем, что каждая вершина - это свой компонент связности.
Идём по рёбрам. Смотрим на компоненты на концах ребра. Пусть это a и b. Все вершины с компонентом b заносим в компонент а. Всё просто.

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@plan_z 0 / 0 / 0 Регистрация: 27.12.2015 Сообщений: 73

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

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	13.07.2016, 09:45
	В чём проблема? Делается заливкой. Сначала считаем, что каждая вершина - это свой компонент связности. Идём по рёбрам. Смотрим на компоненты на концах ребра. Пусть это a и b. Все вершины с компонентом b заносим в компонент а. Всё просто. 0