【并查集】bzoj1015 [JSOI2008]星球大战starwar

浏览数：41 / 时间：2015年06月09日

倒着处理删点，就变成了加点，于是并查集。

#include<cstdio>
using namespace std;
#define N 400001
int fa[N],kill[N],rank[N],n,m,q;
bool hav[N];
int next[N],first[N],v[N],en,x,y,anss[N],cnt;
void AddEdge(int U,int V)
{
	v[++en]=V;
	next[en]=first[U];
	first[U]=en;
}
int find(int x)
{
	if(x==fa[x]) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void Union(int U,int V)
{
	--cnt;
	if(rank[U]<rank[V]) fa[U]=V;
	else
	  {
	  	fa[V]=U;
	  	if(rank[U]==rank[V]) ++rank[U];
	  }
}
int main()
{
	scanf("%d%d",&n,&m); cnt=n;
	for(int i=0;i<n;++i) fa[i]=i;
	for(int i=1;i<=m;++i)
	  {
	  	scanf("%d%d",&x,&y);
	  	AddEdge(x,y);
		AddEdge(y,x);
	  }
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	  {
	  	scanf("%d",&kill[i]);
	  	hav[kill[i]]=1;
	  }
	for(int i=0;i<n;++i)
	  if(!hav[i])
	    for(int j=first[i];j;j=next[j])
		  if(!hav[v[j]])
	      {
	        int f1=find(i),f2=find(v[j]);
	        if(f1!=f2) Union(f1,f2);
	      }
	for(int i=q;i>=1;--i)
	  {
	  	anss[i]=cnt-i;
	  	for(int j=first[kill[i]];j;j=next[j]) if(!hav[v[j]])
	      {
	        int f1=find(kill[i]),f2=find(v[j]);
	        if(f1!=f2) Union(f1,f2);
	      }
	    hav[kill[i]]=0;
	  }
	anss[0]=cnt;
	for(int i=0;i<=q;++i) printf("%d\n",anss[i]);
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。