Как офлайн отвечать на запросы связности при удалении рёбер, развернув время?
Дан связный граф, рёбра по очереди удаляются, между удалениями спрашивают «связны ли X и Y». DSU умеет только добавлять. Слышал про трюк «обратить время». Как он работает на практике и какая сложность?
2 ответа
Идея: читаем все запросы заранее и идём с конца. Удаление при обращении времени превращается в добавление, а это DSU умеет.
Алгоритм:
- Берём граф после всех удалений (то, что осталось) и строим на нём DSU.
- Идём по событиям в обратном порядке:
- событие «удалить ребро (u,v)» → теперь это «добавить (u,v)»:
dsu.unite(u,v); - событие «запрос связности X,Y» → отвечаем
dsu.find(X)==dsu.find(Y)и запоминаем ответ.
- событие «удалить ребро (u,v)» → теперь это «добавить (u,v)»:
- Выводим ответы в исходном порядке.
// сначала пометить все рёбра, которые будут удалены
// в стартовый DSU добавить только НЕудаляемые рёбра
DSU dsu(n);
for (auto& e : neverRemoved) dsu.unite(e.u, e.v);
for (int t = (int)events.size() - 1; t >= 0; --t) {
if (events[t].type == DELETE) dsu.unite(events[t].u, events[t].v);
else ans[events[t].id] = (dsu.find(events[t].x) == dsu.find(events[t].y));
}
Сложность — O((n + m + q)·α(n)), фактически почти линейно; память O(n+m+q). Главное условие применимости — рёбра только удаляются (не добавляются вперемешку) и запросы можно обработать офлайн.
Если удаления и добавления идут вперемешку (полная динамическая связность офлайн), обращения времени мало — тогда нужен DSU с откатами + дерево отрезков по времени жизни рёбер: каждое ребро живёт на отрезке времени, кладём его в соответствующие узлы segment tree, обходим дерево DFS-ом, добавляя рёбра при входе в узел и откатывая при выходе. Сложность O((n+q) log q · α(n)) или log². Обращение времени — частный лёгкий случай этого общего метода.