思路
一道很经典的题，运用了一种叫「时光倒流」的技巧。
「时光倒流」本质上就是将所有删边（或删点）的操作，通过倒序循环求值的方式转化为加边（或加点）。
「时光倒流」具体实现通常伴随着并查集出现，维护一个连通块的某种性质。
首先，我们需要将所有从始至终没有删过的边加入并查集。在这里，我们的并查集不仅仅要维护某个点 \(i\) 的祖先 \(f_i\)，还要维护某个点 \(i\) 所在的连通块是否有电，如果有电记作 \(st_i = 1\)，否则记作 \(st_i = 0\)；以及某个点 \(i\) 所在连通块的大小 \(sz_i\)。
那么，我们就可以在合并的时候维护这些东西，以及答案。假设当前我们要合并 \(x,y\) 所在的连通块。我们可以先找到它们的祖先，记作 \(a,b\)，不难发现，如果合并两个连通块会对答案产生贡献，当且仅当其中有一个连通块有电，另一个没电，分类讨论即可。
- \(st_a = 0,st_b = 1\)，说明在合并两个连通块后，\(x\) 所在联通块中的所有节点都将变为有电，所以，我们可以将 \(st_a \leftarrow 1,ans \leftarrow ans + sz_a\)。
- \(st_a = 1,st_b = 0\)，同理，将 \(st_b \leftarrow 1,ans \leftarrow ans + sz_b\)。
最后维护一下 \(sz\) 和 \(f\) 值的变化即可。
Code
#include <bits/stdc++.h>
#define fst first
#define snd second
#define re register
using namespace std;
typedef pair<int,int> pii;
const int N = 5e5 + 10;
int n,m,e,q,sum;
int f[N],sz[N],del[N],ans[N];
bool st[N],vis[N];
pii g[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int find(int x){
if (f[x] != x) return f[x] = find(f[x]);
return f[x];
}
inline void merge(int x,int y){
int a = find(x);
int b = find(y);
if (!st[a] && st[b]){
st[a] = true;
sum += sz[a];
}
else if (st[a] && !st[b]){
st[b] = true;
sum += sz[b];
}
if (a == b) return;
f[a] = b;
sz[b] += sz[a];
}
int main(){
n = read();
m = read();
e = read();
for (re int i = 1;i <= e;i++){
g[i].fst = read();
g[i].snd = read();
}
for (re int i = 1;i <= n;i++) sz[i] = 1;
for (re int i = 1;i <= n + m;i++) f[i] = i;
for (re int i = n + 1;i <= n + m;i++) st[i] = true;//所有发电站都是有电的
q = read();
for (re int i = 1;i <= q;i++){
del[i] = read();
vis[del[i]] = true;
}
for (re int i = 1;i <= e;i++){
if (!vis[i]) merge(g[i].fst,g[i].snd);
}
for (re int i = q;i;i--){
ans[i] = sum;
merge(g[del[i]].fst,g[del[i]].snd);
}
for (re int i = 1;i <= q;i++) printf("%d\n",ans[i]);
return 0;
}