网站备案拍照 广州/seo网站优化策划书

正题

      第三题：[JSOI2008]星球大战

      这道题的大意是，给出一些边，然后每次删去某些点，求删去点后的联通块。

      我们当然想到的是：并查集的操作以加点为主（没见过删点）。。

      然后我们就想到要倒过来做，我们假设现在已经删完点了，逐个加点进去判断是否在同一个联通块，用一个tot来记录当前联通块数量，明显每加一条连接两个不同集合的边，总集合数就会少1.然后把答案记录下来，倒过来输出即可。

代码<删点留坑>

#include<cstdio>
#include<cstdlib>
#include<cstring>int n,m,k;
struct edge{int x,y,next;
}s[400010];
int fa[400010];
int first[400010];
int len=0;
bool tf[400010];
int q[400010];
int ans[400010];
int t=0;void ins(int x,int y,int c){len++;s[len].y=y;s[len].x=x;s[len].next=first[x];first[x]=len;
}int findpa(int x){if(x!=fa[x]) return fa[x]=findpa(fa[x]);return fa[x];
}int main(){scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){int x,y,c;scanf("%d %d",&x,&y);ins(x,y,c);ins(y,x,c);}scanf("%d",&k);for(int i=1;i<=k;i++){int x;scanf("%d",&x);tf[x]=true;q[i]=x;}for(int i=1;i<=n;i++)fa[i]=i;int tot=n-k;for(int i=1;i<=len;i++)if(tf[s[i].x]==false && tf[s[i].y]==false) {int fx=findpa(s[i].x),fy=findpa(s[i].y);if(fx!=fy) {tot--;fa[fx]=fy; }}ans[++t]=tot;while(1){tot++;tf[q[k]]=false;for(int i=first[q[k]];i!=0;i=s[i].next)if(tf[s[i].x]==false && tf[s[i].y]==false){int fx=findpa(s[i].x),fy=findpa(s[i].y);if(fx!=fy) {fa[fx]=fy;tot--;}}k--;ans[++t]=tot;if(k==0) break;}for(int i=t;i>=1;i--)printf("%d\n",ans[i]);
}