分析
首先一眼看到这个题，第一个想到的肯定是 dfs 暴力每次询问时从左往右把边一条一条加进来，再从右往左加一遍，然后维护连通块个数。但是这样的复杂度显然是 \(O(mk)\) 的。所以我们需要一些优化。
注意到在加边的时候有些边并不会改变连通块的个数。这些边我先称之为无用边。于是我们可以进行两次预处理，一次从左往右，一次从右往左。每次预处理的时候把所有无用边删去，只存非无用边的编号，放在另一个数组里。然后每次询问的时候就从两边暴力这个数组，像普通并查集一样加边、维护就好了。这样的复杂度一下就降到了 \(O(nk\alpha(n))\)，因为有用边不会超过 \(n-1\) 条。
代码
#include <iostream>
using namespace std;
struct edge {
int u, v;
} es[10005];
int fids[10005], eids[10005]; // 两侧的有用边
int f[10005];
int n, m;
int ccnt;
inline void ini() {
ccnt = n; // 初始连通块共 n 个
for (int i = 1; i <= n; i++) f[i] = i;
}
int getf(int x) { return (f[x] == x ? x : f[x] = getf(f[x])); }
inline bool murge(int x, int y) {
x = getf(x), y = getf(y);
if (x != y) {
f[x] = y;
ccnt--; // 一次成功合并会使连通块个数少1个
return true; // 返回值为真说明成功进行了合并
}
return false; // 反之则没有发生合并
}
int fcnt, ecnt;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &es[i].u, &es[i].v);
}
ini();
for (int i = 1; i <= m; i++) { // 从左往右枚举
if (murge(es[i].u, es[i].v)) // 是有用边
fids[++fcnt] = i; // 把编号存起来
}
ini();
for (int i = m; i >= 1; i--) { // 从右往左枚举
if (murge(es[i].u, es[i].v)) // 是有用边
eids[++ecnt] = i; // 把编号存起来
}
int q;
scanf("%d", &q);
int l, r;
for (int i = 1; i <= q; i++) {
ini(); // 每次询问都需要初始化
scanf("%d%d", &l, &r);
for (int j = 1; fids[j] < l && j <= fcnt; j++) murge(es[fids[j]].u, es[fids[j]].v); // 从左往右暴力
for (int j = 1; eids[j] > r && j <= ecnt; j++) murge(es[eids[j]].u, es[eids[j]].v); // 从右往左暴力
printf("%d\n", ccnt);
}
return 0;
}