并查集

并查集是一种树型数据结构，其思想是用一个代表元（树根）去表示一个集合。通常用于处理不相交集合的合并及查询两点是否在同一个集合内。

路径压缩：有路径压缩就不需要按秩合并了，因为在压缩的过程中，会把当前点到根的这条链上的所有点都压缩掉。这样路径压缩总复杂度是O(n)。

按秩合并：启发式合并，如果不能路径压缩，可以通过按秩合并把树的高度控制在O(logn)的级别。

int par[maxn];

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

int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  par[x] = y;
}

带权并查集

带权指 子节点与父节点之间存在限制条件， 如子节点在父节点左边的x米处

接下来面临的两个难点：

• 路径压缩时权值的变化
• 两棵树合并时权值的变化

int find(int x){
    if(x == par[x]) return x;
    int fa = par[x];
    par[x] = find(par[x]); 
    val[x] += val[fa];
    return par[x];
}

删点

设要删的点为x，如果x是树的根，那么删除x之后，这棵树上的其他关系没有办法维持。我们可以通过给每个点都建立相应的虚拟父节点，比如1号点就连向1+n号点。之后每次合并的时候就用其虚拟父节点代替合并。删除点x的话可以将x直接指向一个新的节点，这样就能维持原来的关系。

int tot;
void init(int n) {
  for (int i = 1; i <= n; i++) {
    par[i] = i + n;
    par[i + n] = i + n;
  }
  tot = 2 * n;
}

void remove(int x) {
  par[x] = ++tot;
  par[tot] = tot;
}

删边

将所有操作离线。
我们先把最后的状态建出来，然后逆着查询，这样原来的删边操作就变成了加边操作。

可撤销并查集

如果并查集想要支持回退操作，那么必然不能进行路径压缩。

所以只能通过按秩（高度）合并的方法来保证复杂度。

每次将一个版本（原树的根和原树的秩以及一些其它需要维护的东西）放进栈中，回退的时候从栈中一个一个复原。

struct UFS {
  int par[maxn], h[maxn], top;
  struct Node {
    int x, y, fa, h;
    Node(int x = 0, int y = 0, int fa = 0, int h = 0)
        : x(x), y(y), fa(fa), h(h) {}
  } stk[maxn];

  void init(int n) {
    top = 0;
    for (int i = 1; i <= n; i++) par[i] = i, h[i] = 0;
  }
  int find(int x) { return x == par[x] ? x : find(par[x]); }
  void merge(int u, int v) {
    int x = find(u), y = find(v);
    // if (x == y) return; 和回退的次数相关
    if (h[x] > h[y]) swap(x, y);
    stk[top++] = Node(x, y, par[x], h[y]);
    if (h[x] == h[y]) h[y]++;
    par[x] = y;
  }
  void undo(int k) {
    for (int i = 0; i < k; i++) {
      Node &it = stk[--top];
      par[it.x] = it.fa;
      h[it.y] = it.h;
    }
  }
} ufs;

可持久化并查集

这里用到了可持久化数组，但实际上就是主席树。可持久化数组可以做到修改和查询数组的历史版本，实际上就是用主席树中的叶子节点表示当前版本中此位置的值，可以参考例题P3919。

对于可持久化并查集，我们只要用主席树来维护par和dep的历史版本即可。注意可持久化并查集不能路径压缩，所以需要通过按秩合并来减小复杂度，因此需要维护一个深度数组dep。

find()的复杂度是$O(\log^2 n)$，因为需要在主席树上查询。

参考例题P3402

#include <bits/stdc++.h>
using namespace std;
#define lson lch[k], l, m
#define rson rch[k], m + 1, r
const int maxn = 3e5 + 5;
const int N = maxn * 30;
int root[maxn], par[N], dep[N], lch[N], rch[N], dfn;
int n, m;

void build(int &k, int l, int r) {
  k = ++dfn;
  if (l == r) {
    par[k] = l, dep[k] = 0;
    return;
  }
  int m = l + r >> 1;
  build(lson);
  build(rson);
}

void update_par(int old, int &k, int l, int r, int p, int x) {
  k = ++dfn;
  if (l == r) {
    par[k] = x;
    dep[k] = dep[old];
    return;
  }
  lch[k] = lch[old], rch[k] = rch[old];
  int m = l + r >> 1;
  if (p <= m)
    update_par(lch[old], lson, p, x);
  else
    update_par(rch[old], rson, p, x);
}
void update_dep(int k, int l, int r, int p) {
  if (l == r) {
    dep[k]++;
    return;
  }
  int m = l + r >> 1;
  if (p <= m)
    update_dep(lson, p);
  else
    update_dep(rson, p);
}
int query(int k, int l, int r, int p) {
  if (l == r) return k;
  int m = l + r >> 1;
  if (p <= m)
    return query(lson, p);
  else
    return query(rson, p);
}

int find(int k, int x) {
  int u = query(k, 1, n, x);
  if (par[u] == x) return u;
  return find(k, par[u]);
}
void merge(int old, int &k, int x, int y) {
  int posx = find(old, x), posy = find(old, y);
  if (par[posx] == par[posy]) return;
  if (dep[posx] > dep[posy]) swap(posx, posy);
  update_par(old, k, 1, n, par[posx], par[posy]);  // !
  if (dep[posx] == dep[posy]) update_dep(k, 1, n, par[posy]);
}

int main() {
  scanf("%d%d", &n, &m);
  build(root[0], 1, n);
  for (int i = 1, op, k, a, b; i <= m; i++) {
    scanf("%d", &op);
    if (op == 2) {
      scanf("%d", &k);
      root[i] = root[k];
    } else {
      scanf("%d%d", &a, &b);
      if (op == 1) {
        root[i] = root[i - 1];
        merge(root[i - 1], root[i], a, b);
      } else {
        root[i] = root[i - 1];
        if (par[find(root[i], a)] == par[find(root[i], b)])
          puts("1");
        else
          puts("0");
      }
    }
  }
}