前置知识：可撤销化并查集

注意：可撤销化并查集的作用和删边不一样，其只能撤销最近的一次操作。

既然只需撤销，那么只需在合并并查集时用个 vector 记录下合并的哪两个点，撤销时就直接还原就行了。

这里要强调一下，可撤销化并查集不能路径压缩，只能启发式合并。

代码

int f[MAXN], sz[MAXN];
vector<pii> edge;

int getfa(int u) {
  return (!f[u] ? u : getfa(f[u]));
}

bool Merge(int u, int v) {
  u = getfa(u), v = getfa(v);
  if(u == v) {
    edge.emplace_back(0, 0);
    return 0;
  }
  if(sz[u] > sz[v]) {
    swap(u, v);
  }
  f[u] = v, sz[v] += sz[u];
  edge.emplace_back(u, v);
  return 1;
}

bool Cancal() {
  auto [u, v] = edge.back();
  edge.pop_back();
  sz[v] -= sz[u], f[u] = 0;
  return u && v;
}

线段树分治

这里只讲以下这个问题，其他的可以用类似的方法解决：

给定一个 \(N\) 个结点的图，初始时图上没有边，接下来将会进行一系列加入/删除边的操作，请在每次询问时求出图中连通块数量。

我们可以去思考每一条边在哪些时刻存在，以下面这个为例：

在图中，绿色的区域表示这条边存在的时间段。然后，我们考虑用类似于线段树的方式进行区间修改。

我们对以下这个样例画一棵线段树：

+ 1 2
+ 3 4
+ 1 5
- 1 5
- 1 2
+ 1 3
+ 4 5
- 1 3

这里每个结点都有一个 vector 来记录它所对应的区间要加入的边，接着我们考虑在这个线段树上遍历。

在遍历时，进入某个结点我们就把绿色的边加入，回溯时就把红色的边删除（撤销）。并在每个叶子节点处记录答案即可。

空间复杂度 \(O(N+Q)\)，时间复杂度 \(O(Q\log Q\cdot\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MAXN = 300005;

int f[MAXN], sz[MAXN], cnt;
vector<pii> edge;

int getfa(int u) {
  return (!f[u] ? u : getfa(f[u]));
}

bool Merge(int u, int v) {
  u = getfa(u), v = getfa(v);
  if(u == v) {
    edge.emplace_back(0, 0);
    return 0;
  }
  if(sz[u] > sz[v]) {
    swap(u, v);
  }
  f[u] = v, sz[v] += sz[u];
  edge.emplace_back(u, v);
  return 1;
}

bool Cancal() {
  auto [u, v] = edge.back();
  edge.pop_back();
  sz[v] -= sz[u], f[u] = 0;
  return u && v;
}

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2], ans[MAXN];
  vector<pii> e[MAXN << 2];
  void build(int u, int s, int t) {
    if(s > t) {
      return;
    }
    l[u] = s, r[u] = t;
    if(s == t) {
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
  }
  void update(int u, int s, int t, pii g) {
    if(l[u] >= s && r[u] <= t) {
      e[u].push_back(g);
      return;
    }
    if(s <= r[u << 1]) {
      update(u << 1, s, t, g);
    }
    if(t >= l[(u << 1) | 1]) {
      update((u << 1) | 1, s, t, g);
    }
  }
  void Getans(int u) {
    for(auto [u, v] : e[u]) {
      cnt -= Merge(u, v);
    }
    if(l[u] == r[u]) {
      ans[l[u]] = cnt;
      for(auto [u, v] : e[u]) {
        cnt += Cancal();
      }
      return;
    }
    Getans(u << 1), Getans((u << 1) | 1);
    for(auto [u, v] : e[u]) {
      cnt += Cancal();
    }
  }
}tr;

int n, q;
bool op[MAXN];
map<int, int> l[MAXN];
vector<pii> g;

void FileIO(const string &s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  FileIO("connect");
  cin >> n >> q;
  cnt = n;
  tr.build(1, 1, q);
  for(int i = 1, u, v; i <= q; ++i) {
    char c;
    cin >> c;
    if(c == '+') {
      cin >> u >> v;
      l[u][v] = l[v][u] = i;
      g.emplace_back(u, v);
    }else if(c == '-') {
      cin >> u >> v;
      tr.update(1, l[u][v], i - 1, {u, v});
      l[u][v] = l[v][u] = 0;
    }else {
      op[i] = 1;
    }
  }
  for(auto [u, v] : g) {
    if(l[u][v]) {
      tr.update(1, l[u][v], q, {u, v});
    }
  }
  fill(sz + 1, sz + n + 1, 1);
  tr.Getans(1);
  for(int i = 1; i <= q; ++i) {
    if(op[i]) {
      cout << tr.ans[i] << "\n";
    }
  }
  return 0;
}