Решение задачи #8 на Python с Яндекс CodeRun — Компоненты связности

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Компоненты связности.
Сложность: Лёгкая.
Статус решения: "Решено".

Условие задачи:
Дан неориентированный невзвешенный граф, состоящий из NN вершин и MM ребер. Необходимо посчитать количество его компонент связности и вывести их. Напомним, компонента связности в неориентированном графе - это подмножество вершин, таких что все вершины достижимы друг из друга.

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

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

Решение:

Python

import sys
from collections import defaultdict, deque

def main():
    # Считываем входные данные
    input = sys.stdin.read
    data = input().splitlines()
    
    # Первая строка: количество вершин N и ребер M
    N, M = map(int, data[0].split())
    
    # Словарь для хранения графа в виде списка смежности
    graph = defaultdict(list)
    
    # Читаем ребра и заполняем список смежности
    for i in range(1, M + 1):
        u, v = map(int, data[i].split())
        graph[u].append(v)
        graph[v].append(u)
    
    # Массив для отслеживания посещенных вершин
    visited = [False] * (N + 1)
    
    # Список для хранения всех компонент связности
    components = []
    
    # Обход графа в ширину (BFS) для поиска компонент связности
    def bfs(start):
        queue = deque([start])
        component = []
        visited[start] = True
        while queue:
            node = queue.popleft()
            component.append(node)
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)
        return component

    # Перебираем все вершины, чтобы найти все компоненты связности
    for vertex in range(1, N + 1):
        if not visited[vertex]:
            components.append(bfs(vertex))
    
    # Выводим количество компонент связности
    print(len(components))
    
    # Выводим вершины каждой компоненты
    for component in components:
        print(len(component))
        print(' '.join(map(str, component)))

# Запуск основной функции
if __name__ == "__main__":
    main()

Объяснение кода

Ввод данных:
Считываем из входного файла количество вершин N и ребер M.
Считываем пары вершин, которые задают ребра, и строим граф в виде списка смежности с помощью defaultdict.

Список смежности:
Граф хранится как словарь, где ключ — это вершина, а значение — список всех соседних вершин.

Поиск компонент связности:
Используем массив visited для отметки посещенных вершин.
Обходим граф с помощью обхода в ширину (BFS).
Для каждой не посещенной вершины запускаем BFS, который находит все вершины в той же компоненте связности.

Алгоритм BFS:
Создаем очередь и добавляем стартовую вершину.

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

Вывод результата:
Сначала выводим общее количество компонент.
Для каждой компоненты выводим ее размер и список вершин.

Источник решения: hdhai.com