317
правок
Изменения
→Асимптотика
==== Асимптотика ====
# На первом шаге мы посещаем каждую вершину ровно два раза не более двух раз (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем для каждой вершины считаем время за линейное время.
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
