7.
Топологическая сортировка
Алгоритм можно описать следующим образом:
Дан ориентированный граф с 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 |
Напишите программу
Auto