【BZOJ1015】【JSOI2008】星球大战 并查集

时间：2022-04-02 06:07:11

题目大意

　　给你一张\(n\)个点\(m\)条边的无向图，有\(q\)次操作，每次删掉一个点以及和这个点相邻的边，求最开始和每次删完点后的连通块个数。

　　\(q\leq n\leq 400000,m\leq 200000\)

题解

　　我们可以用并查集维护连通块个数，可惜并查集不支持删除操作。

　　但是这道题没有强制在线，所以可以先删完所有点后再一个个加回来。

　　加边的时候维护连通块个数。

　　时间复杂度：\(O(n\alpha(n))\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

struct graph

{

	int v[1000010];

	int t[1000010];

	int h[1000010];

	int n;

	graph()

	{

		n=0;

		memset(h,0,sizeof h);

	}

	void add(int x,int y)

	{

		n++;

		v[n]=y;

		t[n]=h[x];

		h[x]=n;

	}

};

graph g;

int f[1000010];

int b[1000010];

int x[1000010];

int y[1000010];

int c[1000010];

int s[1000010];

int r[1000010];

int find(int x)

{

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

}

int merge(int x,int y)

{

	x=find(x);

	y=find(y);

	if(x==y)

		return 0;

	if(r[x]>r[y])

		swap(x,y);

	f[x]=y;

	if(r[x]==r[y])

		r[y]++;

	return 1;

}

int main()

{

	int n,m;

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

	int i;

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

	{

		b[i]=1;

		f[i]=i;

		r[i]=1;

	}

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

	{

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

		x[i]++;

		y[i]++;

		g.add(x[i],y[i]);

		g.add(y[i],x[i]);

	}

	int q;

	scanf("%d",&q);

	int ans=n;

	for(i=1;i<=q;i++)

	{

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

		c[i]++;

		b[c[i]]=0;

		ans--;

	}

	int j;

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

		if(b[i])

			for(j=g.h[i];j;j=g.t[j])

				if(b[g.v[j]])

					ans-=merge(i,g.v[j]);

	s[q]=ans;

	for(i=q;i>=1;i--)

	{

		b[c[i]]=1;

		ans++;

			for(j=g.h[c[i]];j;j=g.t[j])

				if(b[g.v[j]])

					ans-=merge(c[i],g.v[j]);

		s[i-1]=ans;

	}

	for(i=0;i<=q;i++)

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

	return 0;

}

相关文章