可撤销并查集

可以支持撤销上一次操作的并查集。

首先一个很重要的前提是，如果我们需要指定哪一个块作为根，是没法可撤销的。

因为它的大致思想是，直接启发式合并，不使用路径压缩，然后记录一下版本值以达到回退的目的。

假设启发式合并中被 Merge 的是 \(v\)，那么会改变的数只有 \(siz(ru), pa(rv)\)。

我们直接记录一下版本值，每次回退就行了，几乎没有技术含量。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Dsu {
    int pa[si], siz[si];
    std::vector<std::pair<int&, int>> hp, hs;
    void init(int n) { 
        hp.clear(), hs.clear();
        for(int i = 0; i <= n; ++i) 
            pa[i] = i, siz[i] = 1; 
    }
    int root(int x) {
        if(pa[x] != x)
            return root(pa[x]);
        return pa[x];
    }
    void Merge(int u, int v) {
        int ru = root(u), rv = root(v);
        if(ru == rv) return;
        if(siz[ru] < siz[rv]) swap(ru, rv), swap(u, v);
        hp.push_back(make_pair(pa[rv], pa[rv]));
        hs.push_back(make_pair(siz[ru], siz[ru]));
        siz[ru] += siz[rv], pa[rv] = ru;
    }
    void rollBack(int ver) {
        while((int)hp.size() > ver) {
            hp.back().first = hp.back().second;
            hs.back().first = hs.back().second;
            hp.pop_back(), hs.pop_back();
        }
    }
} dsu;
最后更新: June 30, 2024