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