【bzoj3237】 Ahoi2013—连通图

时间：2024-01-18 21:12:44

http://www.lydsy.com/JudgeOnline/problem.php?id=3237 (题目链接)

题意

　　给出一个无向图，$Q$组询问，每次询问将原图断掉$C$条边后是否还连通。

Solution

　　CDQ图分治，并查集维护。实在写不动题了，我能说我是蒯的吗T_T：http://blog.csdn.net/creationaugust/article/details/50889351

细节

　　bzoj的G++版本是多久以前的了，莫名CE。。

代码

// bzoj3237

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=200010,maxm=5000010;

int ans[maxn],del[maxn],fa[maxn],st[maxm];

int n,m,Q,tim,top;

struct data {int c,id,e[4];}q[maxn];

struct edge {int u,v;}e[maxn];

namespace Unionset {

	int find(int x) {

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

		st[++top]=x;st[++top]=fa[x];return fa[x]=find(fa[x]);

	}

	void Union(int u,int v) {

		if (find(u)!=find(v)) {

			st[++top]=fa[v];

			st[++top]=fa[fa[v]];

			fa[fa[v]]=fa[u];

		}

	}

}

using namespace Unionset;

void solve(int l,int r) {

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

	if (l==r) {

		for (int i=0;i<q[l].c && flag;i++)

			if (find(e[q[l].e[i]].u)!=find(e[q[l].e[i]].v)) flag=0;

		ans[q[l].id]=flag;

		for (;now!=top;top-=2) fa[st[top-1]]=st[top];

		return;

	}

	tim++;

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

		for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim;

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

		for (int j=0;j<q[i].c;j++)

			if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v);

	solve(l,mid);tim++;

	for (;now!=top;top-=2) fa[st[top-1]]=st[top];

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

		for (int j=0;j<q[i].c;j++) del[q[i].e[j]]=tim;

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

		for (int j=0;j<q[i].c;j++)

			if (del[q[i].e[j]]!=tim) Union(e[q[i].e[j]].u,e[q[i].e[j]].v);

	solve(mid+1,r);

	for (;now!=top;top-=2) fa[st[top-1]]=st[top];

}

int main() {

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

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

	for (int i=1;i<=m;i++) scanf("%d%d",&e[i].u,&e[i].v);

	scanf("%d",&Q);tim=1;

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

		scanf("%d",&q[i].c);q[i].id=i;

		for (int j=0;j<q[i].c;j++) scanf("%d",&q[i].e[j]),del[q[i].e[j]]=tim;

	}

	for (int i=1;i<=m;i++) if (del[i]!=tim) Union(e[i].u,e[i].v);

	solve(1,Q);

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

	return 0;

}

相关文章