147
правок
Изменения
→Время работы
==Время работы==
[[Link-Cut Tree|LinkingLink-Cutting TreeCut tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
Очевидно, что просмотров ребер суммарно <tex>O(E)</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
