A. Топологическая сортировка
1000 мс · 256 МБ · всё или ничего
Дан ориентированный граф. Выпишите вершины в таком порядке, чтобы каждое ребро вело слева направо. Если это невозможно, сообщите об этом.
Порядков обычно много, поэтому в ответе нужен лексикографически наименьший - тот, который начинается с наименьшей возможной вершины, при равном начале продолжается наименьшей возможной, и так далее.
Формат ввода
В первой строке - числа и (, ): количество вершин и рёбер.
В следующих строках - пары , : ребро из в . Возможны кратные рёбра и петли.
Формат вывода
Выведите лексикографически наименьший топологический порядок - чисел. Если порядка не существует, выведите -1.
Примеры
ввод
6 6 1 2 3 2 4 2 2 5 6 5 4 6
вывод
1 3 4 2 6 5
ввод
3 3 1 2 2 3 3 1
вывод
-1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.