BZOJ 3237([Ahoi2013]连通图-cdq图重构-连通性缩点)

3237: [Ahoi2013]连通图

Time Limit: 20 Sec Memory Limit: 512 MB

Submit: 106
Solved: 31

[
Submit][
Status]

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

Source

弱B。。的弱B题解。。。

首先我们知道，可以把提问中没问的边缩成点。

但是不影响复杂度。。。

所以我们，把它拆成2半。。

前一半缩点(不考虑后一半的询问)，乱搞，后一半的不用考虑前一半的询问，乱搞。。。

于是f(q)=f(q/2)+O(qc*a(qc)) O(f(q))=O(qlogqc*α(qc))

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<functional>

#include<iostream>

#include<cmath>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define RepD(i,n) for(int i=n;i>=0;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define Lson (x<<1)

#define Rson ((x<<1)+1)

#define MEMr(a,n,w) Rep(i,n) a[i]=w;

#define MEMF(a,n,w) For(i,n) a[i]=w;

#define MEM(a) memset(a,0,sizeof(a));

#define MEMI(a) memset(a,127,sizeof(a));

#define MEMi(a) memset(a,128,sizeof(a));

#define INF (2139062143)

#define F (100000007)

#define MAXN (100000+10)

#define MAXM (200000+10)

#define MAXQ (100000+10)

#define MAXC (4)

long long mul(long long a,long long b){return (a*b)%F;}

long long add(long long a,long long b){return (a+b)%F;}

long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}

typedef long long ll;

int n,m,q;

struct comm

{

	int n,a[4];

}ask[MAXQ],back[MAXQ*30],*back_tail=back;

struct E

{

	int x,y;

}e[MAXM*30],*e_tail=e;

struct unionset

{

	int father[MAXN];

	void init(int n){For(i,n) father[i]=i;}

	int getfather(int x)

	{

		if (father[x]==x) return x;

		return father[x]=getfather(father[x]);

	}

	bool union2(int x,int y)

	{

		if (getfather(x)==getfather(y)) return 0;

		father[father[x]]=father[y]; return 1;

	}

}ufs;

bool ans[MAXQ]={0};

int newV[MAXN],newE[MAXM];

void solve(int n,E *_e,int m,int l,int r)

{

	e_tail+=m;

	E *e=e_tail;

	copy(_e,e_tail,e);

	static bool b[MAXM]={0};MEMr(b,m,0);

	if (l==r)

	{

		Rep(j,ask[l].n) b[ask[l].a[j]]=1;

		ufs.init(n);

		int tot=0;

		Rep(i,m) if (!b[i]) tot+=ufs.union2(e[i].x,e[i].y);

		if (tot==n-1) ans[l]=1;

		e_tail-=m;

		return;

	}

	Fork(i,l,r) Rep(j,ask[i].n) b[ask[i].a[j]]=1;

	ufs.init(n);

	Rep(i,m) if (!b[i]) ufs.union2(e[i].x,e[i].y);

	//Con

	int n2=0;

	For(i,n) if (ufs.getfather(i)==i) newV[i]=++n2;

	For(i,n) if (ufs.getfather(i)^i) newV[i]=newV[ufs.getfather(i)];

	Rep(i,m) e[i].x=newV[e[i].x],e[i].y=newV[e[i].y];

	//Red

	int m2=0;

	Rep(i,m) if (b[i]) newE[i]=m2++;

	Rep(i,m) if (b[i]) e[newE[i]]=e[i];

	Fork(i,l,r) Rep(j,ask[i].n) ask[i].a[j]=newE[ask[i].a[j]];

	{

		int m=l+r>>1,len=m-l+1;

		comm *back_head=back_tail;

		back_tail+=len;

		copy(ask+l,ask+m+1,back_head);

		solve(n2,e,m2,l,m);

		copy(back_head,back_head+len,ask+l);

		back_tail-=len;

		solve(n2,e,m2,m+1,r);

	}

	e_tail-=m;

}

int main()

{

//	freopen("bzoj3237.in","r",stdin);

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

	Rep(i,m) scanf("%d%d",&e[i].x,&e[i].y);

	scanf("%d",&q);

	Rep(i,q)

	{

		scanf("%d",&ask[i].n);

		Rep(j,ask[i].n) scanf("%d",&ask[i].a[j]),ask[i].a[j]--;

	}

	solve(n,e,m,0,q-1);

	Rep(i,q) if (ans[i]) puts("Connected");else puts("Disconnected");

	return 0;

}

巴特西