# Offline Deletion

Authors: Benjamin Qi, Siyong Huang

### Prerequisites

Erasing from non-amortized insert-only data structures.

## 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.

Resources | |||
---|---|---|---|

CP-Algorithms | includes code (but no explanation) for dynamic connectivity |

## Dynamic Connectivity

Resources | |||
---|---|---|---|

GCP |

**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.

### This section is not complete.

*explanation? check Guide to CP?*

### Warning: Watch Out!

Because path compression is amortized, it does not guarauntee $O(Ng_{2}N)$ runtime. You *must* use merging by rank.

### Implementation

C++

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;}bool merge(int a, int b)

## Problems

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Offline Deletion!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.