693
правки
Изменения
→Обобщение задачи для произвольных графов
== Обобщение задачи для произвольных графов ==
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за то же самое время<tex>O(\mathrm{\log}n)</tex>.
Попробуем выполнить операцию удаления ребра. Для этого в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности.
