# Offline Deletion

Authors: Benjamin Qi, Siyong Huang

Erasing from non-amortized insert-only data structures.

### Prerequisites

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

YS | Normal | ## Show TagsDSUrb |

### DSU With Rollback

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

YS | Easy | ## Show TagsDSUrb | |||

MMCC | Easy | ## Show TagsDSUrb |

### This section is not complete.

explanation? check Guide to CP?

### Warning: Watch Out!

Because path compression is amortized, it does not guarauntee
$\mathcal{O}(N \log^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; }

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Normal | ## Show TagsDSUrb | |||

CF | Normal | ## Show TagsDSUrb | |||

CF | Hard | ## Show TagsDynacon | |||

Baltic OI | Very Hard | ## Show TagsD&C, DSUrb |

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