Войти
или
Зарегистрироваться
Курсы
Учебник
Учебник 2.0
ОГЭ/ЕГЭ
Олимпиады
Рубрикатор
Компилятор
Курсы
Все о графах
Поиск в глубину. DFS
Модуль:
Поиск в глубину. DFS
Задача
7
/19
Топологическая сортировка
Теория
Нажмите, чтобы прочитать/скрыть
Алгоритм можно описать следующим образом:
Дан ориентированный граф с n вершинами и m рёбрами. Требуется перенумеровать его вершины таким образом, чтобы каждое рёбро вело из вершины с меньшим номером в вершину с большим.
Иными словами, требуется найти перестановку вершин (топологический порядок), соответствующую порядку, задаваемому всеми рёбрами графа.
Будем использовать обход в глубину (dfs(v))
Если мы будем в момент выхода из
\(dfs(v)\)
добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка.
Таким образом,
искомая топологическая сортировка — это сортировка в порядке убывания времён выхода.
Задача
Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.
Входные данные:
В первой строке содержатся два натуральных числа n и m (1≤n≤10
5
, 1≤m≤10
5
) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).
Выходные данные:
Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести −1.
Примеры
№
Входные данные
Выходные данные
1
4 4
1 4
4 3
4 2
3 2
1 4 3 2
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам
Кол-во
Java
1
Python
247
С++ Mingw-w64
201
Комментарий учителя