Решение задачи #10. Python CodeRun, Топологическая сортировка

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

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

Напомним: Топологическая сортировка указывает такой линейный порядок на его вершинах, что любое ребро ведёт от вершины с меньшим номером к вершине с большим номером.
Формат ввода

В первой строке входного файла два натуральных числа NN и MM (1≤N,M≤100 000)(1≤N,M≤100000) — количество вершин и рёбер в графе соответственно. Далее в MM строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Формат вывода:
Выведите любую топологическую сортировку графа в виде последовательности номеров вершин (перестановка чисел от 1 до N). Если топологическую сортировку графа построить невозможно, выведите -1.

Примечание:
Если отбросить формализм, то можно сказать, что нужно сделать следующее: перенумеровать все вершины нашего графа.

Для всех M рёбер из входных данных и только для них должно выполняться условие, что ребро ведёт из вершины с меньшим номером в вершину с большим номером.

Решение:

Python

from collections import defaultdict, deque

def topological_sort(n, edges):
    """
    Функция для выполнения топологической сортировки графа.
    :param n: количество вершин в графе
    :param edges: список рёбер графа (список кортежей (u, v), где u -> v)
    :return: список вершин в порядке топологической сортировки или -1, если сортировка невозможна
    """
    # Инициализируем граф и массив для подсчёта входящих степеней
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)

    # Строим граф и подсчитываем входящие степени
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # Ищем все вершины с нулевой входящей степенью (можно начинать с них)
    queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])

    # Список для хранения результата топологической сортировки
    topo_order = []

    # Алгоритм Кана
    while queue:
        # Извлекаем вершину с нулевой входящей степенью
        current = queue.popleft()
        topo_order.append(current)

        # Уменьшаем входящую степень всех соседей текущей вершины
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            # Если входящая степень соседа стала равна нулю, добавляем его в очередь
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Если мы обошли все вершины, возвращаем порядок
    if len(topo_order) == n:
        return topo_order
    else:
        # Если остались вершины с ненулевой входящей степенью, граф содержит цикл
        return -1

# Ввод данных
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n, m = int(data[0]), int(data[1])  # Читаем количество вершин и рёбер
    edges = []
    for i in range(m):
        u, v = int(data[2 + i * 2]), int(data[3 + i * 2])
        edges.append((u, v))
    
    # Вызываем функцию топологической сортировки и выводим результат
    result = topological_sort(n, edges)
    if result == -1:
        print(-1)
    else:
        print(" ".join(map(str, result)))

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

Инициализация данных:
Читаем количество вершин N и рёбер M. Формируем список рёбер графа.

Построение графа:
Используем defaultdict для представления графа в виде списка смежности. Одновременно подсчитываем количество входящих рёбер для каждой вершины (массив in_degree).

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

Алгоритм Кана:
Пока очередь не пуста:
Извлекаем вершину из очереди и добавляем её в итоговый порядок (topo_order).
Для всех её соседей уменьшаем входящую степень. Если входящая степень соседа становится равна нулю, добавляем его в очередь. Этот процесс продолжается, пока мы не обработаем все вершины.

Проверка результата:
Если количество обработанных вершин (len(topo_order)) меньше N, значит в графе есть цикл, и топологическая сортировка невозможна. В противном случае возвращаем итоговый порядок.

Вывод результата:
Если сортировка возможна, выводим порядок вершин.
Если нет, выводим -1.

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

Добавьте Hdhai в избранное и вы будете чаще видеть наши последние новости на главной Дзена и в разделе «Новости партнёров» или читайте нас в Telegram в привычном для вас формате.