Как сделать DSU с откатами (rollback) для офлайн-задач на динамическую связность?
В задаче рёбра то добавляются, то удаляются (динамическая связность офлайн через дерево отрезков по времени). Нужен DSU, который умеет отменять последнее объединение. Но обычный DSU со сжатием путей откатить нельзя — сжатие меняет кучу указателей. Как быть?
2 ответа
Ключевая идея: отказаться от сжатия путей и оставить только объединение по рангу/размеру. Тогда каждое unite меняет ровно два поля (p[b] и rnk/sz корня), и эти изменения легко записать в стек и откатить. find без сжатия — O(log n) (высота ограничена рангом), этого достаточно.
struct DSU_Rollback {
vector<int> p, rnk;
vector<pair<int,int>> hist; // (вершина_b, старый_ранг_a)
DSU_Rollback(int n): p(n), rnk(n,0){ iota(p.begin(),p.end(),0); }
int find(int x){ while(x!=p[x]) x=p[x]; return x; } // БЕЗ сжатия
bool unite(int a, int b){
a=find(a); b=find(b);
if(a==b) return false;
if(rnk[a] < rnk[b]) swap(a,b);
hist.push_back({b, rnk[a]});
p[b]=a;
if(rnk[a]==rnk[b]) ++rnk[a];
return true;
}
void rollback(){ // отменить последнее успешное unite
auto [b, ra] = hist.back(); hist.pop_back();
rnk[p[b]] = ra;
p[b] = b;
}
};
Сложность: find/unite — O(log n), rollback — O(1). Снимаете «снимок» как hist.size() перед входом в узел дерева отрезков по времени и откатываете до него при выходе. Память O(n + число операций в стеке). Эта связка (DSU с откатами + segment tree по времени) — стандарт для офлайн динамической связности за O((n+q)·log²n).
Грабля: НЕ кладите в историю неуспешные unite (когда a==b). Тогда счётчик откатов разъедется с числом реальных изменений. Я обычно возвращаю из unite число сделанных изменений (0 или 1) и при выходе из узла откатываю ровно столько раз. И помните: rollback-DSU именно офлайн — он не даёт настоящего удаления произвольного ребра онлайн, он работает только потому, что мы заранее знаем времена жизни всех рёбер и раскладываем их по дереву отрезков.