Число компонент связности

@dzlevin · Регистрация: 26.10.2017

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

Задача:
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их. Во входном файле записано два числа 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.069 сек)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inp =list(map(int,input().split()))
n,m = inp[0],inp[1]
 
def ToDict(n,m):
    ribs = list()
    while m > 0:
        ribs.append(list(map(int, input().split())))
        m -= 1
    ribsDict = dict()
    for i in range(n):
        currRibs = []
        for j in range(len(ribs)):
            if ribs[j][0] == i + 1:
                currRibs.append(ribs[j][1])
            elif ribs[j][1] == i + 1:
                currRibs.append(ribs[j][0])
        ribsDict[i + 1] = currRibs
    return ribsDict
 
 
ribsDict = ToDict(n,m)
 
Visited = [False]*(n + 1)
 
 
def DFS(start,verts):
    Visited[start] = True
    verts.append(start)
    for u in ribsDict[start]:
        if not Visited[u]:
            DFS(u,verts)
    return verts
 
comps = list()
 
for i in range(1,n+1):
    if not Visited[i]:
        comps.append(DFS(i,list()))
 
print(len(comps))
for i in range(len(comps)):
    print(len(comps[i]))
    print(' '.join(list(map(str,sorted(comps[i])))))

@Crasty · 18.03.2021, 23:04

Привет. Не знаю прочтёшь ты это или нет, но я хотел задать вопрос - зачем тебе массив ToDict? и что ты в нём хранишь?

@DobroAlex · 19.03.2021, 01:52

Crasty, определено, человек заходивших последний раз в 2018, прочтёт

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Crasty 0 / 0 / 0 Регистрация: 05.08.2020 Сообщений: 2
	18.03.2021, 23:04
	Привет. Не знаю прочтёшь ты это или нет, но я хотел задать вопрос - зачем тебе массив ToDict? и что ты в нём хранишь? 0

@DobroAlex Заклинатель змей 705 / 560 / 219 Регистрация: 30.04.2016 Сообщений: 2,605
	19.03.2021, 01:52
	Crasty, определено, человек заходивших последний раз в 2018, прочтёт 1