[Luogu 1197] JSOI2008 星球大战

<题目链接>

---

#include <cstdio>

#include <cstring>

const int MAXN=400010,MAXM=200010;

bool gone[MAXN];

int n,m,k,sum,q[MAXN],ans[MAXN];

struct Edge

{

	int to;

	Edge *next;

	Edge(int to,Edge* next):to(to),next(next){}

	~Edge(void)

	{

		if(next!=nullptr)

			delete next;

	}

}*head[MAXN];

class UFS

{

	private:

		bool exist[MAXN];

		int f[MAXN];

		int Find(int x)

		{

			return x==f[x] ? x : f[x]=Find(f[x]);

		}

	public:

		UFS(int n)

		{

			memset(exist,0,sizeof exist);

			for(int i=0;i<n;++i)

			{

				head[i]=nullptr;

				f[i]=i;

			}

		}

		~UFS(void)

		{

			for(int i=0;i<n;++i)

				delete head[i];

		}

		void Merge(int x,int y)

		{

			f[Find(y)]=Find(x);

		}

		int Count(void)

		{

			int ans=0;

			for(int i=0,t;i<n;++i)

				if(!gone[i] && !exist[t=Find(i)])

				{

					++ans;

					exist[t]=1;

				}

			return ans;

		}

		bool Connected(int x,int y)

		{

			return Find(x)==Find(y);

		}

};

void AddEdges(int u,int v)

{

	head[u]=new Edge(v,head[u]);

	head[v]=new Edge(u,head[v]);

}

int main(int argc,char** argv)

{

	scanf("%d %d",&n,&m);

	static UFS *S=new UFS(n);

	for(int i=1,x,y;i<=m;++i)

	{

		scanf("%d %d",&x,&y);

		AddEdges(x,y);

	}

	scanf("%d",&k);

	for(int i=1;i<=k;++i)

	{

		scanf("%d",&q[i]);

		gone[q[i]]=true;

	}

	for(int u=0;u<n;++u)

		if(!gone[u])

			for(Edge *i=head[u];i!=nullptr;i=i->next)

			{

				int v=i->to;

				if(!gone[v])

					S->Merge(u,v);

			}

	ans[k]=sum=S->Count();

	for(int j=k,u;j>=1;--j)

	{

		++sum;

		gone[u=q[j]]=false;

		for(Edge *i=head[u];i!=nullptr;i=i->next)

		{

			int v=i->to;

			if(gone[v]==false && !S->Connected(u,v))

			{

				--sum;

				S->Merge(u,v);

			}

		}

		ans[j-1]=sum;

	}

	for(int i=0;i<=k;++i)

		printf("%d\n",ans[i]);

	delete S;

	return 0;

}