Hello, in this blog I want to introduce a simple way to online delete/remove an element from its union in O(1), with the cost of using more memory.

consider this is your usual DSU:

struct DSU{
    int p[1000005], sz[1000005];
    void init(int n){
        for(int i = 1; i <= n; i ++) p[i] = i;
        fill(sz + 1,sz + n + 1, 1);
    }
    int find(int u){
        if(u == p[u]) return u;
        return p[u] = find(p[u]);
    }
    void uni(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x, y);
        p[y] = x, sz[x] += sz[y];
    }
} dsu;

Say, you have already a set A = {1, 2, 3, 4, 5}, and you need to remove 3 from A (for some reason). In short, turn {1, 2, 3, 4, 5} to {3} and {1, 2, 4, 5}. How do you do it? You just need to change p[3] to a new value!!!

But what if there are other elements (denote x) that have p[x] = 3? To solve that problem, we can instead of using an element to represent a set, but use numbers from n + 1 onward. By using separate numbers to represent a set, any changes to element u of set A will not affect any other elements in A.

the new DSU:

struct DSU{
    vector <int> sz, p;
    int timer;
    void init(int n){
        timer = n * 2;
        p.resize(n * 2 + 1);
        sz.resize(n * 2 + 1, 1);
        for(int i = n + 1; i <= n * 2; i ++) p[i] = i;
        for(int i = 1; i <= n; i ++) p[i] = i + n; // use i + n instead of i
    }
    int find(int u){
        if(u == p[u]) return u;
        return p[u] = find(p[u]);
    }
    void uni(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x, y);
        p[y] = x, sz[x] += sz[y];
    }
    void del(int u){
        int pr = find(u);
        if(sz[pr] == 1) return; // no need to delete u from its set if the set contains only u
        sz[pr] --; // reduce size of old set
        timer ++;
        p.push_back(timer); // adding the new set to p and sz
        sz.push_back(1);
        p[u] = timer;
    }
} dsu;

As you can see, I have edited init() and add a new function del(), but uni() and find() remain unchanged. To optimize the memory usage from O(n + m) to O(n * 2) = O(n) (m denotes the number of operations to the DSU), we can reuse any empty sets that are left behind after merging 2 sets, but will further complicates the DSU which destroys its main advantage of being simple to implement.

Note: I haven't found any implement of this technique online so I decided to write this blog. This is also my first blog ever on Codeforces, and it will be expected to have many mistakes (both in my code and in the blog), so please point out any mistakes you find in this blog, thank you in advance!!!