BZOJ 1015 并查集

首先正常的想法，用并查集维护当前图的连通性，当某一节点被摧毁后，将与其相连的边删除，判断连通性是否有变化，更新答案。但是比较麻烦的是并查集不支持删除操作，那怎么办呢，我们可以逆向思维，将删除点的过程转化成添加点的过程，这样就能用并查集维护了。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 400005 int last[maxn],pre[maxn],other[maxn],cnt; int a[maxn],n,m,k,father[maxn],l,ans[maxn],tot; bool flag[maxn]; void connect(int x,int y) { l++; pre[l]=last[x]; last[x]=l; other[l]=y; } int getfather(int x) { if (x!=father[x]) father[x]=getfather(father[x]); return father[x]; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); x++;y++; connect(x,y); connect(y,x); } scanf("%d",&k); for (int i=1;i<=k;i++) { scanf("%d",a+i); a[i]++; flag[a[i]]=1; } cnt=n-k; for (int i=1;i<=n;i++) father[i]=i; for (int u=1;u<=n;u++) { if (flag[u]) continue; for (int p=last[u];p;p=pre[p]) { int v=other[p]; if (flag[v]) continue; int fu=getfather(u); int fv=getfather(v); if (fu==fv) continue; father[fu]=fv; cnt--; } } ans[k+1]=cnt; for (int i=k;i>=1;i--) { flag[a[i]]=0; cnt++; int u=a[i]; for (int p=last[u];p;p=pre[p]) { int v=other[p]; if (flag[v]) continue; int fu=getfather(u); int fv=getfather(v); if (fu==fv) continue; cnt--; father[fu]=fv; } ans[i]=cnt; } for (int i=1;i<=k+1;i++) printf("%d\n",ans[i]); return 0; }