Has Not Appeared
0/5
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.
Feel free to file a request to complete this using the "Contact Us" button.
explanation? check Guide to CP?
explanation? check Guide to CP?
Warning: Watch Out!
Because path compression is amortized, it does not guarauntee runtime. You must use merging by rank.
Implementation
C++
1int p[MN], r[MN];2int *t[MN*40], v[MN*40], X;3int setv(int *a, int b)4{5 if(*a != b) t[X] = a, v[X] = *a, *a = b, ++X;6 return b;7}8void rollback(int x) {for(;X>x;) --X, *t[X] = v[X];}9int find(int n) {return p[n] ? find(p[n]) : n;}10bool 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!