可撤销并查集

大前提：任意时刻任意两个点之间至多只有一条路径

一般的并查集（路径压缩优化）是无法回退的，当我们想要复用并查集时，有3种思路

1. 可持久化数组（可持久化线段树）维护并查集
2. 按秩合并并查集（用堆来维护历史信息）
3. Link-Cut Tree（最实用）

本文记录的是第二种方法

按秩合并

核心代码

struct Union_Find_Set{ // 并查集
    static const int max_node = 5e5 + 100;
    int ufs[max_node], depth[max_node];

    vector<pair<int, pair<int, int> > > stk;

    void init(int n){
        for(int i=0; i<=n; i++) {
            ufs[i] = i;
            depth[i] = 1;
        }
    }

    int find(int x){
        return ufs[x]==x?x:find(ufs[x]);
    }
	// remember 表示该条记录是否可能要被回退
    bool merge(int u, int v, bool remember){
        u = find(u), v = find(v);
        if(u == v) return false;
        if(depth[u] < depth[v]) swap(u, v);
        if(remember) stk.push_back({v, {u, depth[u]}});
        depth[u] = max(depth[u], depth[v] + 1);
        ufs[v] = u; // 让深度小的接在深度大的下面
        return true;
    }

    void recover(){ // 回退
        if(stk.empty()) return;
        pair<int, pair<int, int> > rec = stk.back();
        stk.pop_back();
        ufs[rec.first] = rec.first;
        depth[rec.second.first] = rec.second.second;
    }

}ufs;

例题 Codeforces 892E

题意：给一个联通的无向图$G$，$q$次询问：给定$k$条边，问这些边是否可能同时出现在一颗最小生成树中。

由Kruskal算法可知，如果当前边$e_i(w_i=x)$在最小生成树中，那么在加入所有边$\{e_j\mid w_j<x\}$后，$e_i$的两端点属于不同的连通分量。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 1000;

struct edge{
    int u, v, w, id;
    bool operator <(const edge & e) const{
        return w < e.w;
    }
}es[maxn];

int id2e[maxn];
bool ans[maxn];
vector<pair<int, int> > querys[maxn];

struct Union_Find_Set{
    // 略
}ufs;

void handle(int x, int l, int r){
    int cnt = 0;
    vector<pair<int, int> > & vec = querys[x];
    for(int i=l; i<=r; i++){
        int e = vec[i].second;
        if(!ufs.merge(es[e].u, es[e].v, true)){ // 需要回退的边
            ans[vec[i].first] = 1;
            break;
        }
        cnt++;
    }
    for(int i=0; i<cnt; i++) ufs.recover(); // 回退cnt步
}

void solve(){
    int n, m, q;
    cin >> n >> m;
    ufs.init(n + 1);

    for(int i=1; i<=m; i++){
        es[i].id = i;
        cin >> es[i].u >> es[i].v >> es[i].w;
    }
    sort(es + 1, es + m + 1);
    for(int j=1; j<=m; j++) id2e[es[j].id] = j;
	// 离线做法
    cin >> q;
    for(int i=0, k; i<q; i++){
        cin >> k;
        for(int j=0, x; j<k; j++){
            cin >> x;
            querys[es[id2e[x]].w].push_back({i, id2e[x]});
        }
    }

    for(int l=1, r=1; l<=m; l=r){
        int w = es[l].w;
        // 找到所有权值等于w的边
        while(r <= m && es[r].w == w) r++;
        for(int ql=0, qr=0; ql < (int)querys[w].size(); ql = qr){
            // 找到w相同且在同一次询问的中边
            while(qr < (int)querys[w].size() && querys[w][ql].first == querys[w][qr].first) qr++;
            handle(w, ql, qr - 1);
        }

        for(int i=l; i<r; i++) ufs.merge(es[i].u, es[i].v, false); // 无需回退的边
    }

    for(int i=0; i<q; i++) {
        cout << (ans[i]?"NO\n":"YES\n");
    }
}

signed main(){
    solve();
}