This documentation is automatically generated by online-judge-tools/verification-helper
#include "structure/union-find/union-find-undo.hpp"
struct UnionFindUndo {
vector< int > data;
stack< pair< int, int > > history;
UnionFindUndo(int sz) {
data.assign(sz, -1);
}
bool unite(int x, int y) {
x = find(x), y = find(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 find(int k) {
if(data[k] < 0) return (k);
return (find(data[k]));
}
int size(int k) {
return (-data[find(k)]);
}
void undo() {
data[history.top().first] = history.top().second;
history.pop();
data[history.top().first] = history.top().second;
history.pop();
}
void snapshot() {
while(history.size()) history.pop();
}
void rollback() {
while(history.size()) undo();
}
};
#line 1 "structure/union-find/union-find-undo.hpp"
struct UnionFindUndo {
vector< int > data;
stack< pair< int, int > > history;
UnionFindUndo(int sz) {
data.assign(sz, -1);
}
bool unite(int x, int y) {
x = find(x), y = find(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 find(int k) {
if(data[k] < 0) return (k);
return (find(data[k]));
}
int size(int k) {
return (-data[find(k)]);
}
void undo() {
data[history.top().first] = history.top().second;
history.pop();
data[history.top().first] = history.top().second;
history.pop();
}
void snapshot() {
while(history.size()) history.pop();
}
void rollback() {
while(history.size()) undo();
}
};