主要学习的blog/
整理下可持久化并查集要完成的内容：
1、将一个点的父亲（并查集那个fa）进行更改 （实际上是新增一个信息点）update。
2、查找某个时间点下一个pos对应的信息点编号。
3、查找一个点的父节点。
4、更新一个点的deep值，不用新写函数，可以用3号操作找到编号后++。
5、初始化build。
// #pragma GCC optimize(2) // #pragma GCC optimize(3) // #pragma GCC optimize(4) #include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> #include <unordered_map> // #include<bits/extc++.h> // using namespace __gnu_pbds; using namespace std; #define pb push_back #define fi first #define se second #define debug(x) cerr<<#x << " := " << x << endl; #define bug cerr<<"-----------------------"<<endl; #define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /**********showtime************/ int n,m; const int maxn = 2e5+9; int tr[maxn]; struct T{ int l,r; }tree[maxn * 30]; int fa[maxn * 30], dp[maxn * 30]; int tot = 0; void build(int & rt, int le, int ri) { rt = ++tot; if(le == ri) { fa[rt] = le; dp[rt] = 1; return; } int mid = (le + ri) >> 1; build(tree[rt].l, le, mid); build(tree[rt].r, mid+1, ri); } void update(int last, int &rt, int le, int ri, int pos, int ff) { rt = ++tot; if(le == ri) { fa[rt] = ff; dp[rt] = dp[last]; return; } int mid = (le + ri) >> 1; tree[rt] = tree[last]; if(mid >= pos) update(tree[last].l, tree[rt].l, le, mid, pos, ff); else update(tree[last].r, tree[rt].r, mid+1, ri, pos, ff); } int query(int rt, int le, int ri, int pos) { if(le == ri) return rt; int mid = (le + ri) >> 1; if(mid >= pos) return query(tree[rt].l, le, mid, pos); else return query(tree[rt].r, mid+1, ri, pos); } int findfa(int rt, int pos) { int x = query(rt, 1, n, pos); if(fa[x] == pos) return x; return findfa(rt, fa[x]); } // void adddeep() int main(){ scanf("%d%d", &n, &m); build(tr[0], 1, n); for(int i=1; i<=m; i++) { int op; scanf("%d", &op); tr[i] = tr[i-1]; if(op == 1) { int u,v; scanf("%d%d", &u, &v); int fu = findfa(tr[i], u); int fv = findfa(tr[i], v); if(fa[fu] == fa[fv]) {continue;} if(dp[fu] > dp[fv]) swap(fu, fv); update(tr[i-1], tr[i], 1, n, fa[fu], fa[fv]); if(dp[fu] == dp[fv]) { dp[fv] ++; } } else if(op == 2) { int k; scanf("%d", &k); tr[i] = tr[k]; } else { int u,v; scanf("%d%d", &u, &v); int fu = findfa(tr[i], u); int fv = findfa(tr[i], v); // cout<<fa[fu]<<" , " << fa[fv]<<endl; if(fa[fu] == fa[fv]) puts("1"); else puts("0"); } } return 0; }
下面再附上一个可撤销并查集的模板
/// 可撤回并查集模板 struct UFS { stack<pair<int*, int>> 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(); } }T;