题目链接：https://www.luogu.com.cn/problem/P1197
可以反过来想，从最终的状态逐渐加入点，同并查集合并这个点和它相连的点。用一个cnt动态维护连通块个数：加入一个新的点时，cnt++，此后每次合并集合时，如果根节点在同一个集合则不合并，自然cnt不变；如果根节点在不同的集合时合并，此时连通块个数减少1，cnt--。
具体实现我是开了好几个数组，用结构体存储道路的左右两点，p[i]=0表示点i没有被摧毁，q[i]逆序存储点的顺序，ans逆序存答案，然后用一个vector存储每个点邻接的点。一开始先合并最后的情况：如果p[r[i].x]=0且p[r[i].y]=0，则合并；之后就是上述的逐渐加点的过程，如果新加的点q[i]的邻接的点v[q[i]][j]没有被摧毁即p[v[q[i]][j]]=0，则合并q[i]和v[q[i]][j]，并动态更新cnt。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=4000+10; 4 struct st{int x,y;} r[maxn]; 5 vector<int> v[maxn]; 6 int p[maxn],par[maxn],q[maxn],ans[maxn]; 7 int n,m,i,j,k,t; 8 set<int> s; 9 10 int find(int u){return par[u]==u?u:par[u]=find(par[u]);} 11 12 int main(){ 13 //freopen("luogu1197.txt","r",stdin); 14 scanf("%d%d",&n,&m); 15 for (i=1;i<=m;i++) { 16 scanf("%d%d",&r[i].x,&r[i].y); 17 v[r[i].x].push_back(r[i].y);v[r[i].y].push_back(r[i].x); 18 } 19 scanf("%d",&k); 20 memset(p,0,sizeof(p)); 21 for (i=1;i<=k;i++){ 22 int star;scanf("%d",&star); 23 p[star]=1;q[k-i+1]=star; 24 } 25 for (i=0;i<n;i++) par[i]=i; 26 for (i=1;i<=m;i++) 27 if (p[r[i].x]==0&&p[r[i].y]==0){ 28 int xx=find(r[i].x);int yy=find(r[i].y); 29 if (xx!=yy) par[xx]=yy; 30 } 31 s.clear(); 32 for (i=0;i<n;i++) { 33 par[i]=find(par[i]); 34 if (p[i]==0) s.insert(par[i]); 35 } 36 int cnt=s.size(); 37 ans[k+1]=cnt; 38 for (i=1;i<=k;i++){ 39 p[q[i]]=0;cnt++; 40 for (j=0;j<v[q[i]].size();j++) 41 if (p[v[q[i]][j]]==0) { 42 int xx=find(q[i]);int yy=find(v[q[i]][j]); 43 if (xx!=yy){ 44 par[xx]=yy;cnt--; 45 } 46 } 47 ans[k-i+1]=cnt; 48 } 49 for (i=1;i<=k+1;i++) printf("%d\n",ans[i]); 50 //fclose(stdin); 51 return 0; 52 }
原文：https://www.cnblogs.com/edmunds/p/12752166.html
