可撤销并查集

const int N = 2e5 + 5;

struct DSU {
  struct Info {
    int u, v, add;
  };
  vector<int> p, h;
  vector<Info> st;
  int idx = 0;
    DSU(int n) {
      p.resize(n + 1);
      h.resize(n + 1);
      iota(p.begin(), p.end(), 0);
    }
    void init(int n) {
        p.resize(n + 1);
        h.resize(n + 1);
        iota(p.begin(), p.end(), 0);
    }

    int find(int x){
      while (x != p[x]) {
        x = p[x];
      }
        return p[x];
    }

    void merge(int u, int v){
        int fu = find(u);
        int fv = find(v);
        if (fu == fv){
            return;
        }
        if (h[fu] > h[fv]){
            swap(fu, fv);
        }
        st.emplace_back(fu, fv, h[fu] == h[fv]);
        idx++;
        p[fu] = fv;
        if (h[fu] == h[fv]) {
          h[fv]++;
        }
    }

    void restore(int t){ // 回溯到 t 时刻
        while (st.size() > t){
          resume();
        }
    }

    void resume() {
      auto [u, v, add] = st.back();
      h[v] -= add;
      p[u] = u;
        st.pop_back();
        idx--;
  }
} dsu(N);
// 这里取决于维护的点数！