Топологическая сортировка
Дан ориентированный граф с
v вершинами и e рёбрами. Необходимо расположить вершины в таком порядке, чтобы, если существует ребро из v1 в v2, вершина-источник v1 попадала в массив вершин раньше, чем v2. Таким образом, после сортировки каждая дуга будет вести от вершины с меньшим индексом к вершине с большим.🤔
Обратите внимание, что существует несколько возможных вариантов корректной топологической сортировки.
Однако если в графе есть циклы, то никакого корректного порядка не найдётся.
Алгоритм можно реализовать с помощью поиска в глубину (DFS), запуская его из каждой вершины, которая ещё не была посещена. В каждой итерации DFS мы сначала рекурсивно добавляем в ответ все дочерние вершины (вершины, в которые есть ребро из текущей), и только когда все они обработаны, добавляем в список ответа текущую вершину. Благодаря этому вершина-источник окажется позже всех вершин, достижимых из неё. В конце алгоритма мы переворачиваем полученный порядок:
used = [False] * n # помеченные вершины
order = [] # топологический порядок
def dfs(v): # поиск в глубину
used[v] = True # отмечаем вершину как посещённую
for to in g[v]: # для каждой вершины to, смежной с v
if not used[to]: # если to ещё не посещена
dfs(to) # запускаем dfs от to
order.append(v) # добавляем v в топологический порядок
for i in range(n): # для каждой вершины
if not used[i]: # если вершина ещё не посещена
dfs(i) # запускаем dfs от неё
print(*order[::-1]) # выводим топологический порядокЗадача: организовать расписание курсов
У вас есть
n курсов, которые вы хотите пройти. Существует p обязательных предварительных условий. Каждое из них задаётся парой курсов , где курс следует пройти до курса (если пара 1, 2, это значит, что курс 2 нужно пройти раньше курса 1).Нужно определить, сможете ли вы закончить все курсы.
Входные данные
В первой строке заданы два целых числа
n и p (1 ≤ n, p ≤ 10 000).В следующих
p строках содержатся пары чисел (1 ≤ ≤ n).Выходные данные
Необходимо вывести
Yes, если все курсы можно пройти, и No в противном случае.Примеры
Input | Output |
2 1
2 1 | Yes |
2 2
2 1
1 2 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB