bzoj 3237: [Ahoi2013]連通圖

Description

Input

Output

Sample Input

4 5

1 2

2 3

3 4

4 1

2 4

3

1 5

2 2 3

2 1 2

Sample Output

Connected

Disconnected

Connected

HINT

N<=100000 M<=200000 K<=100000

首先把詢問中未出現的邊縮點

因為每個詢問互相獨立，考慮CDQ分治

對于區間[l,r]的詢問，令mid=(l+r)/2

先把前面未出現後面出現的邊加入，然後分治[l,mid]

再恢複并查集，把後面未出現前面出現的邊加入，分治[mid+1,r]

恢複并查集的時候維護一個棧把所有fa[]修改記錄下來即可

#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
struct line
{
	int s,t;
}a[200001];
struct question
{
	int c;
	int x[5];
	bool ans;
}ask[100001];
int fa[100001],s1[4000001],s2[4000001];
bool v[200001];
//int tot=0;//時間戳記錄前後的不同 
int p;
inline int find(int x)
{
	if(fa[x]!=x)
	{
		int t=find(fa[x]);
		p++;
		s1[p]=x;
		s2[p]=fa[x];
		fa[x]=t;
	}
	return fa[x];
}
inline void solve(int l,int r)
{
	if(l==r)
	{
		bool flag=true;
	//	int p1=p;
		int i;
		for(i=1;i<=ask[l].c;i++)
		{
			int d=ask[l].x[i];
			int fx=find(a[d].s);
			int fy=find(a[d].t);
			if(fx!=fy)
			{
				flag=false;
				break;
			}
		}
	//	p=p1;
		ask[l].ans=flag;
		return ;
	}
	int i,j;
	int mid=(l+r)/2;
	//tot++;
	for(i=l;i<=mid;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		//	a[ask[i].x[j]].p=tot;
			v[ask[i].x[j]]=true;
	}
	int p1=p;
	for(i=mid+1;i<=r;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		{
			int d=ask[i].x[j];
			//if(a[d].p!=tot)
			if(!v[d])
			{
				int fx=find(a[d].s);
				int fy=find(a[d].t);
				if(fx!=fy)
				{
					p++;
					s1[p]=fx;
					s2[p]=fa[fx];
					fa[fx]=fy;
				}
			}
		}
	}
	for(i=l;i<=mid;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		//	a[ask[i].x[j]].p=tot;
			v[ask[i].x[j]]=false;
	}
	solve(l,mid);
	
	for(i=p;i>=p1+1;i--)
		fa[s1[i]]=s2[i];
	p=p1;
	//tot++;
	for(i=mid+1;i<=r;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		//	a[ask[i].x[j]].p=tot;
			v[ask[i].x[j]]=true;
	}
//	p=0;
	//p1=p;
	for(i=l;i<=mid;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		{
			int d=ask[i].x[j];
			//if(a[d].p!=tot)
			if(!v[d])
			{
				int fx=find(a[d].s);
				int fy=find(a[d].t);
				if(fx!=fy)
				{
					p++;
					s1[p]=fx;
					s2[p]=fa[fx];
					fa[fx]=fy;
				}
			}
		}
	}
	//p=p1;
	for(i=mid+1;i<=r;i++)
	{
		for(j=1;j<=ask[i].c;j++)
		//	a[ask[i].x[j]].p=tot;
			v[ask[i].x[j]]=false;
	}
	solve(mid+1,r);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=m;i++)
		scanf("%d%d",&a[i].s,&a[i].t);
	int q;
	scanf("%d",&q);
	for(i=1;i<=q;i++)
	{
		scanf("%d",&ask[i].c);
		for(j=1;j<=ask[i].c;j++)
		{
			scanf("%d",&ask[i].x[j]);
			v[ask[i].x[j]]=true;
		}
	}
	for(i=1;i<=n;i++)
		fa[i]=i;
	for(i=1;i<=m;i++)
	{
		if(!v[i])
		{
			int fx=find(a[i].s);
			int fy=find(a[i].t);
			fa[fx]=fy;
		}
	}
	memset(v,false,sizeof(v));
	solve(1,q);
	for(i=1;i<=q;i++)
	{
		if(ask[i].ans)
			printf("Connected\n");
		else
			printf("Disconnected\n");
	}
	return 0;
}