luoguP5227 [AHOI2013]连通图

题意

虽然没用线段树，但是仍然是线段树分治的思想。

考虑分治询问序列，假设当前在\([l,r]\)，我们将\([1,l-1]\)和\([r+1,Q]\)的与\([l,r]\)内不重复的边都连上了。

先将\([mid+1,r]\)中与\([l,mid]\)不重复的边都连上，之后递归\([l,mid]\)，再将之前的操作撤销，将\([l,mid+1]\)中与\([mid+1,r]\)不重复的边都连上，之后递归\([mid+1,r]\)。

发现当低递归到\([l,l]\)时，整个并查集正好是第\(l\)组询问的图的状态。

code:

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

const int maxm=2*1e5+10;

const int maxQ=1e5+10;

int n,m,Q,top;

int fa[maxn],size[maxn];

bool ans[maxn],check[maxm];

struct Edge{int u,v;}E[maxm];

struct node{int x,y,sizey;}sta[maxQ];

vector<int>edge[maxQ];

inline int read()

{

	char c=getchar();int res=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();

	return res*f;

}

int find(int x){return fa[x]==x?x:find(fa[x]);}

inline void merge(int u,int v,bool op)

{

	int x=find(u),y=find(v);

	if(x==y)return;

	if(size[x]>size[y])swap(x,y);

	if(op)sta[++top]=(node){x,y,size[y]};

	fa[x]=y;size[y]+=size[x];

}

inline void cut(int id)

{

	int x=sta[id].x,y=sta[id].y;

	fa[x]=x;size[y]=sta[id].sizey;

}

void solve(int l,int r)

{

	if(l==r){ans[l]=(size[find(1)]==n);return;}

	int now=top,mid=(l+r)>>1;

	for(int i=mid+1;i<=r;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=1;

	for(int i=l;i<=mid;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=0;

	for(int i=mid+1;i<=r;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			if(check[edge[i][j]])merge(E[edge[i][j]].u,E[edge[i][j]].v,1);

	solve(l,mid);

	while(top>now)cut(top),top--;

	for(int i=l;i<=mid;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=1;

	for(int i=mid+1;i<=r;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=0;

	for(int i=l;i<=mid;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			if(check[edge[i][j]])merge(E[edge[i][j]].u,E[edge[i][j]].v,1);

	solve(mid+1,r);

	while(top>now)cut(top),top--;

	for(int i=l;i<=mid;i++)

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=0;

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;

	for(int i=1;i<=m;i++)E[i].u=read(),E[i].v=read();

	Q=read();

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

	{

		int k=read(),id;

		while(k--)id=read(),edge[i].push_back(id);

	}

	for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;

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

		for(unsigned int j=0;j<edge[i].size();j++)

			check[edge[i][j]]=1;

	for(int i=1;i<=m;i++)if(!check[i])merge(E[i].u,E[i].v,0);

	solve(1,Q);

	for(int i=1;i<=Q;i++)puts(ans[i]?"Connected":"Disconnected");

	return 0;

}

巴特西

luoguP5227 [AHOI2013]连通图

题意

最新文章

热门文章