1632
правки
Изменения
м
rollbackEdits.php mass rollback
В графе могут быть кратные рёбра и петли.
}}
В этой статье приведено решение задачи в offline, то есть ответы на все запросы будут получены после обработки всех запросов, а не по мере их поступления.
Каждое из <tex>O(m)</tex> рёбер записывается в <tex>O(\log m)</tex> вершин дерева отрезков. Поэтому операций <tex>\mathrm{union}</tex> в СНМ будет <tex>O(m \log m)</tex>. Каждая выполняется за <tex>O(\log n)</tex> (СНМ с ранговой эвристикой). Откаты не влияют на время работы.
Можно считать, что <tex>n = O(\log m)</tex>, так как в запросах используется не более <tex>2m</tex> вершин.
Время работы: <tex>O(m \log m \log n) = O(m \log^2 m)</tex>.
== Реализация на C++ ==
