394
правки
Изменения
→Асимптотика
==Асимптотика==
Время работы внутри главного цикла будет равно <tex>O(E + V)</tex>(обычный dfs) + <tex>O(E)</tex> + <tex>O(V)</tex>(колличество компонент связанности) = <tex>O(E)</tex>.
Количество итераций которое выполняется главным циклом = <tex>O(log(V))</tex> т.к на каждой итерации количество компонент связанности уменьшается в 2 раза.
