components_count.py

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

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

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

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

Выходные данные:
3
3
1 2 3 
2
4 5 
1
6

"""

def dfs(vertex, visited, component, edges):
    """
    Обойти компоненту связности, которой принадлежит вершина vertex

    vertex - номер вершины, с которой начинается обход
    visited - список посещенных вершин
    component - список вершин, которые принадлежат компоненте связности
    edges - список ребер графа
    """

    # Пометить вершину как посещенную
    visited[vertex] = True

    # Добавить вершину в список вершин, которые принадлежат компоненте связности
    component.append(vertex)

    # Обойти все смежные вершины
    for edge in edges:
        # Если ребро не содержит вершину vertex, то пропустить
        if vertex not in edge:
            continue

        # Получить смежную вершину
        if edge[1] == vertex:
            adjacent_vertex = edge[0]
        else:
            adjacent_vertex = edge[1]

        # Если смежная вершина еще не посещена, то продолжить обход из нее
        if not visited[adjacent_vertex]:
            dfs(adjacent_vertex, visited, component, edges)



def solve():
    # Прочесть: N - количество вершин в графе, M – количество ребер
    # пример: "6 4".split() -> ["6", "4"] -> list(map(int, ["6", "4"])) -> [6, 4]
    # n = 6, m = 4
    n, m = list(map(int, input().split()))

    # Прочесть m ребер
    edges = []
    for _ in range(m):
        # Прочесть ребро
        # пример: "3 1".split() -> ["3", "1"] -> list(map(int, ["3", "1"])) -> [3, 1]
        edges.append(list(map(int, input().split())))
    

    # Посещенные вершины
    # пример n = 6, visited = [False, False, False, False, False, False, False]
    # номера вершин:             0      1      2      3      4      5      6
    # 0 - не используется, т.к. вершины нумеруются с 1
    visited = [False] * (n + 1)

    # Количество компонент связности
    components_count = 0

    # Список компонент связности
    components = []

    # Обойти все вершины
    for vertex in range(1, n+1):
        # Если вершина еще не посещена, то обойти компоненту связности, которой она принадлежит
        if not visited[vertex]:
            # Список вершин, которые принадлежат компоненте связности
            component = []
            # Обойти компоненту связности, которой принадлежит вершина vertex
            dfs(vertex, visited, component, edges)

            # Добавить компоненту связности в список компонент связности
            components.append(component)

            # Увеличить количество компонент связности
            components_count += 1

    # Отсортировать компоненты связности по количеству вершин в них от большего к меньшему (необязательно)
    components.sort(key=lambda component: len(component), reverse=True)

    # Вывести количество компонент связности
    print(components_count)

    # Вывести компоненты связности
    for component in components:
        # Вывести количество вершин в компоненте
        print(len(component))
        # Вывести вершины в произвольном порядке
        print(*component)


# Тестовые данные
input_data = """6 4
3 1
1 2
5 4
2 3"""

import sys
from io import StringIO
# Перенаправить ввод из тестовых данных в стандартный поток ввода
sys.stdin = StringIO(input_data)

# Решить задачу
solve()