693
правки
Изменения
→Алгоритм
== Алгоритм ==
=== Решение упрощённой задачи ===
==== Задача без удалений рёбер ====
Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются.
Время работы такого решения: <tex>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
=== Построение дерева отрезков ===
