Has Not Appeared

Offline Deletion

Authors: Benjamin Qi, Siyong Huang, Chongtian Ma

Erasing from non-amortized insert-only data structures.

Edit This Page

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

DSU With Rollback

DSU with Rollback is an extension to DSU that saves merges and can undo the previous kk merges.

StatusSourceProblem NameDifficultyTags
Show TagsDSUrb
Show TagsDSUrb

Warning: Watch Out!

Because path compression is amortized, it does not guarantee O(Nlog2N)\mathcal{O}(N \log^2 N) runtime. You must use merging by rank. An explanation is given here.


Adding on to the usual DSU, we can store the parent and sizes of nodes that are being merged before each merge. This allows us revert each node to their parents before the merge so that the rollback function can use the information to undo the merges.

We can store each state of the DSU using an integer, captured by the snapshot function which returns the number of old merges that has not been rolled back. It's similar taking a picture of something, and years later going back into your photo album and scrolling up until you find this picture.

For example, if history array stores {(1,2),(3,4),(1,3)}\{(1, 2), (3, 4), (1, 3)\}, this means that before our most recent unite, the representative element for component 33 is 11, and before that the representative element for component 44 is 33. If we want to roll back two unites, we would pop the last two elements of the history array and update the representative elements in order.

Furthermore, we can extend this array to roll back component sizes or anything else our DSU may track!


class DSU {
vector<int> p, sz;
// stores previous unites
vector<pair<int &, int>> history;
DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int get(int x) { return x == p[x] ? x : get(p[x]); }

Dynamic Connectivity

Dynamic Connectivity is the most common problem using the deleting trick. These types of problems involve determining whether pairs of nodes are in the same connected component while edges are being inserted and removed.

Focus Problem – try your best to solve this problem before continuing!

Solution - Vertex Add Component Sum

For dynamic connectivity problems, we say for every query, there's an interval [l,r][l, r] where it's active. Obviously, for each edge add/remove query, l=l = (the index of the query which adds the edge), and r=r = (the index of the query which removes the edge) 1-1. If an edge never gets removed, then r=q1r = q - 1. Note that we assign intervals such that for queries outside the interval, they are completely unaffected by this query. We can use similar reasoning to construct intervals for type 22 and 33 queries.

We can now construct a query tree. If our interval is encapsulated by the the tree's interval, then we can add our query to the node corresponding to the interval. When answering queries, as we enter the interval, we can process all the operations inside the interval. As we exit the interval, we need to undo them. If we are at a leaf, we can answer type 33 queries since we have processed all queries outside this interval [i,i][i, i]. Since we are processing intevals by halves each time, the depth is at most logn\log n, similar to divide and conquer.

See the code below for implementation details. Note that similar to unite operations, we can also perform and undo operations of type 22!


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
Code Snippet: DSU (Click to expand)
const int MAXN = 3e5;
DSU dsu(MAXN);
StatusSourceProblem NameDifficultyTags
Show TagsDynacon
Show TagsDSUrb
Show TagsDSUrb
Show TagsDSUrb
Show TagsDynacon
Show TagsDynacon
Baltic OIVery 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!