可撤销并查集模板：

struct UFS {    stack
    
     
      > stk;    int fa[N], rnk[N];    inline void init(int n) {        for (int i = 0; i <= n; ++i) fa[i] = i, rnk[i] = 0;    }    inline int Find(int x) {        while(x^fa[x]) x = fa[x];        return x;    }    inline void Merge(int x, int y) {        x = Find(x), y = Find(y);        if(x == y) return ;        if(rnk[x] <= rnk[y]) {            stk.push({fa+x, fa[x]});            fa[x] = y;            if(rnk[x] == rnk[y]) {                stk.push({rnk+y, rnk[y]});                rnk[y]++;            }        }        else {            stk.push({fa+y, fa[y]});            fa[y] = x;        }    }    inline void Undo() {        *stk.top().fi = stk.top().se;        stk.pop();    }}ufs;
     
    

可持久化并查集模板：

struct Sustainable_DSU {    static const int N = 1e5 + 5, M = 2e6 + 5;    int root[N], lson[M], rson[M], fa[M], rnk[M], tot, n;    inline void build(int &rt, int l, int r) {        rt = ++tot;        if(l == r) {fa[rt] = l; return ;}        int m = l+r >> 1;        build(lson[rt], l, m);        build(rson[rt], m+1, r);    }    inline void init(int _n) {        n = _n;        tot = 0;        build(root[0], 1, n);    }    inline void Update(int old, int &rt, int p, int v, int l, int r) {        rt = ++tot;        lson[rt] = lson[old], rson[rt] = rson[old];        if(l == r) {            fa[rt] = v;            rnk[rt] = rnk[old];            return ;        }        int m = l+r >> 1;        if(p <= m) Update(lson[rt], lson[rt], p, v, l, m);        else Update(rson[rt], rson[rt], p, v, m+1, r);    }    inline void update(int rt, int p, int l, int r) {        if(l == r) { rnk[rt]++; return ;}        int m = l+r >> 1;        if(p <= m) update(lson[rt], p, l, m);        else update(rson[rt], p, m+1, r);    }    ///返回rt版本p位置fa数组下标    inline int query(int rt, int p, int l, int r) {        if(l == r) return rt;        int m = l+r >> 1;        if(p <= m) return query(lson[rt], p, l, m);        else return query(rson[rt], p, m+1, r);    }    ///返回rt版本p所在并查集fa数组下标    inline int Find(int rt, int p) {        int now = query(rt, p, 1, n);        if(fa[now] == p) return now;        else return Find(rt, fa[now]);    }    ///在i时刻合并x和y所在并查集    inline void Merge(int i, int x, int y) {        root[i] = root[i-1];        int px = Find(root[i], x), py = Find(root[i], y);        if(fa[px] != fa[py]) {            if(rnk[px] > rnk[py]) swap(px, py);            Update(root[i-1], root[i], fa[px], fa[py], 1, n);            if(rnk[px] == rnk[py]) update(root[i], fa[py], 1, n);        }    }};

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headstruct Sustainable_DSU { static const int N = 2e5 + 5, M = 4e6 + 5; int root[N], lson[M], rson[M], fa[M], rnk[M], tot, n; inline void build(int &rt, int l, int r) { rt = ++tot; if(l == r) {fa[rt] = l; return ;} int m = l+r >> 1; build(lson[rt], l, m); build(rson[rt], m+1, r); } inline void init(int _n) { n = _n; tot = 0; build(root[0], 1, n); } inline void Update(int old, int &rt, int p, int v, int l, int r) { rt = ++tot; lson[rt] = lson[old], rson[rt] = rson[old]; if(l == r) { fa[rt] = v; rnk[rt] = rnk[old]; return ; } int m = l+r >> 1; if(p <= m) Update(lson[rt], lson[rt], p, v, l, m); else Update(rson[rt], rson[rt], p, v, m+1, r); } inline void update(int rt, int p, int l, int r) { if(l == r) { rnk[rt]++; return ;} int m = l+r >> 1; if(p <= m) update(lson[rt], p, l, m); else update(rson[rt], p, m+1, r); } ///返回rt版本p位置fa数组下标 inline int query(int rt, int p, int l, int r) { if(l == r) return rt; int m = l+r >> 1; if(p <= m) return query(lson[rt], p, l, m); else return query(rson[rt], p, m+1, r); } ///返回rt版本p所在并查集fa数组下标 inline int Find(int rt, int p) { int now = query(rt, p, 1, n); if(fa[now] == p) return now; else return Find(rt, fa[now]); } ///在i时刻合并x和y所在并查集 inline void Merge(int i, int x, int y) { root[i] = root[i-1]; int px = Find(root[i], x), py = Find(root[i], y); if(fa[px] != fa[py]) { if(rnk[px] > rnk[py]) swap(px, py); Update(root[i-1], root[i], fa[px], fa[py], 1, n); if(rnk[px] == rnk[py]) update(root[i], fa[py], 1, n); } }}s;int n, m, op, a, b;int main() { scanf("%d %d", &n, &m); s.init(n); for (int i = 1; i <= m; ++i) { scanf("%d", &op); if(op == 1) scanf("%d %d", &a, &b), s.Merge(i, a, b); else if(op == 2) scanf("%d", &a), s.root[i] = s.root[a]; else { scanf("%d %d", &a, &b); s.root[i] = s.root[i-1]; a = s.Find(s.root[i], a); b = s.Find(s.root[i], b); if(s.fa[a] == s.fa[b]) printf("1\n"); else printf("0\n"); } } return 0;}