[JSOI2008]星球大战starwar BZOJ1015

并查集

正序处理时间复杂度为n^2，考虑逆序处理，这样，时间复杂度从n^2降为nlogn

附上代码：

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <queue>

using namespace std;

#define N 400005

int fa[N<<1],n,m,K,head[N<<1],cnt,q[N],ans[N];

struct node

{

	int to,next;

}e[N<<1];

void add(int x,int y)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	head[x]=cnt++;

	return ;

}

int find(int x)

{

	int p=x,t;

	while(fa[p]!=p)p=fa[p];

	while(x!=p)t=fa[x],fa[x]=p,x=t;

	return p;

}

bool vis[N];

int main()

{

	for(int i=1;i<N;i++)fa[i]=i;

	memset(head,-1,sizeof(head));

	memset(vis,1,sizeof(vis));

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

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

	{

		int x,y;

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

		x++,y++;

		add(x,y);

		add(y,x);

	}

	scanf("%d",&K);

	ans[K]=n-K;

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

	{

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

		q[i]++;

		vis[q[i]]=0;

	}

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

	{

		if(!vis[i])continue;

		for(int j=head[i];j!=-1;j=e[j].next)

		{

			int to1=e[j].to;

			if(!vis[to1])continue;

			int fx=find(i),fy=find(to1);

			if(fx!=fy)

			{

				fa[fx]=fy;

				ans[K]--;

			}

		}

	}

	vis[q[K]]=1;

	for(int i=K-1;i>=0;i--)

	{

		ans[i]=ans[i+1]+1;

		for(int j=head[q[i+1]];j!=-1;j=e[j].next)

		{

			int to1=e[j].to;

			if(!vis[to1])continue;

			int fx=find(q[i+1]),fy=find(to1);

			if(fx!=fy)

			{

				fa[fx]=fy;

				ans[i]--;

			}

		}

		vis[q[i]]=1;

	}

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

	{

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

	}

	return 0;

}