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