【BZOJ1015】【JSOI2008】星球大战Starwar（离线并差集）

传送门

一道简单题

所谓正难则反

我们考虑离线从后往前操作

就变成了每次加一个点求当前联通块个数

并查集就完了呗

代码稍微写的有些繁琐

但肯定还是可以看的

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    	char ch=getchar();
    	int res=0;
    	while(!isdigit(ch))ch=getchar();
    	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    	return res;
}
const int N=800005;
int fa[N],op[N],ans[N],dest[N],adj[N],tot,nxt[N<<1],k,cnt=1,vis[N<<1],to[N<<1],n,m;
struct edge{
    	int u,v;
}e[N];
inline void addedge(int u,int v){
    	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
inline int find(int x){
    	return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
int main(){
    	n=read(),m=read();
    	for(int i=1;i<=n;++i)fa[i]=i;
    	for(int i=1;i<=m;++i){
        	int u=read()+1,v=read()+1;
        	addedge(u,v),addedge(v,u);
    }
    	k=read();
    	for(int i=1;i<=k;++i){
        	int u=read()+1;op[i]=u;dest[u]=1;
        	for(int e=adj[u];e;e=nxt[e]){
            	vis[e]=vis[e^1]=1;
        }
    }
    	for(int u=1;u<=n;++u){
        	for(int e=adj[u];e;e=nxt[e]){
            	if(!vis[e]){
                	int v=to[e];
                	int f1=find(u),f2=find(v);
                	if(f1!=f2)fa[f2]=f1,++tot;
                }
            }
        }
    	ans[k+1]=n-k-tot;
	    for(int i=k;i;--i){
        	int u=op[i];dest[u]=0;
        	for(int e=adj[u];e;e=nxt[e]){
            	int v=to[e];
            	if(dest[v])continue;
            	int f1=find(u),f2=find(v);
                	if(f1!=f2)fa[f2]=f1,++tot;
            }
        	ans[i]=n-i+1-tot;
    }
    	for(int i=1;i<=k+1;++i){
        	cout<<ans[i]<<'
';
    }
}