This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "data-structure/dsu_rollback.hpp"
#pragma once struct dsu_rollback { vector<int> data; stack<pair<int, int>> history; int inner_snap; dsu_rollback(int sz) : inner_snap(0) { data.assign(sz, -1); } bool merge(int x, int y) { x = root(x), y = root(y); history.emplace(x, data[x]); history.emplace(y, data[y]); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int root(int k) { if (data[k] < 0) return k; return root(data[k]); } int same(int x, int y) { return root(x) == root(y); } int size(int k) { return (-data[root(k)]); } void undo() { data[history.top().first] = history.top().second; history.pop(); data[history.top().first] = history.top().second; history.pop(); } void snapshot() { inner_snap = int(history.size() >> 1); } int get_state() { return int(history.size() >> 1); } void rollback(int state = -1) { if (state == -1) state = inner_snap; state <<= 1; assert(state <= (int)history.size()); while (state < (int)history.size()) undo(); } };
#line 2 "data-structure/dsu_rollback.hpp" struct dsu_rollback { vector<int> data; stack<pair<int, int>> history; int inner_snap; dsu_rollback(int sz) : inner_snap(0) { data.assign(sz, -1); } bool merge(int x, int y) { x = root(x), y = root(y); history.emplace(x, data[x]); history.emplace(y, data[y]); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int root(int k) { if (data[k] < 0) return k; return root(data[k]); } int same(int x, int y) { return root(x) == root(y); } int size(int k) { return (-data[root(k)]); } void undo() { data[history.top().first] = history.top().second; history.pop(); data[history.top().first] = history.top().second; history.pop(); } void snapshot() { inner_snap = int(history.size() >> 1); } int get_state() { return int(history.size() >> 1); } void rollback(int state = -1) { if (state == -1) state = inner_snap; state <<= 1; assert(state <= (int)history.size()); while (state < (int)history.size()) undo(); } };