Offline Deletion

Offline Deleting from a Data Structure

Using a persistent data structure or rollbacking, you are able to simulate deleting from a data structure while only using insertion operations.

Dynamic Connectivity

Dynamic Connectivity is the most common problem using the deleting trick. The problem is to determine whether pairs of nodes are in the same connected component while edges are being inserted and removed.

DSU With Rollback

DSU with rollback is a subproblem required to solve the above task.

Implementation

Copy
int p[MN], r[MN];
int *t[MN * 40], v[MN * 40], X;
int setv(int *a, int b) {
	if (*a != b) t[X] = a, v[X] = *a, *a = b, ++X;
	return b;
}
void rollback(int x) {
	for (; X > x;) --X, *t[X] = v[X];
}
int find(int n) { return p[n] ? find(p[n]) : n; }

Problems