hdu 5354 cdq分治+并查集

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5354

题意：问删除每个点后能否构成二分图。

做法：

   考虑分治，solve(l,r)是用来求区间l到r的答案，那么可以把l到mid的点都加入并查集，如果存在奇环了，那么mid+1到r的答都

是0，如果没有奇环，继续solve(mid+1,r)。 然后用相同的做法处理l到mid的答案。

   并查集需要还原，所以用启发式合并，用一个栈来记录需要还原的数据。这样复杂度是nlognlogn。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int base[N],vec[2*N],pre[2*N],tot;
void link(int x,int y)
{
	vec[++tot]=y; pre[tot]=base[x]; base[x]=tot;
}
int fa[N],sz[N],len[N];
int top,stk[N];
bool check(int l,int r,int x,int y)
{
	for (int u=l;u<=r;u++)
	{
		for (int now=base[u];now;now=pre[now])
		{
			int v=vec[now];
			if (v>=x&&v<=y) continue;
			int su=0,sv=0,fu=u,fv=v;
			while(fu!=fa[fu]) su^=len[fu],fu=fa[fu];
			while(fv!=fa[fv]) sv^=len[fv],fv=fa[fv];
			if (fu==fv)
			{
				if (su==sv) return 0;
				continue;
			}
			if (sz[fu]<sz[fv]) swap(fu,fv);
			stk[++top]=fv;
			fa[fv]=fu;
			sz[fu]+=sz[fv];
			len[fv]=su^sv^1;
		}
	}
	return 1;
}
void load(int u)
{
	sz[fa[u]]-=sz[u];
	fa[u]=u;
}
int ans[N];
void solve(int l,int r)
{
	if (l==r) { ans[l]=1; return; }
	int pretop=top;
	int mid=(l+r)/2;
	if (!check(l,mid,mid+1,r))
		for (int i=mid+1;i<=r;i++) ans[i]=0;
	else
		solve(mid+1,r);
	while(top>pretop) load(stk[top]),top--;

	if (!check(mid+1,r,l,mid))
		for (int i=l;i<=mid;i++) ans[i]=0;
	else
		solve(l,mid);
	while(top>pretop) load(stk[top]),top--;
}
int main()
{
	int t; scanf("%d",&t);
	int n,m;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		while(m--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			link(x,y); link(y,x);
		}
		for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
		solve(1,n);
		for (int i=1;i<=n;i++) printf("%d",ans[i]);
		printf("\n");
		tot=0;
		for (int i=1;i<=n;i++) base[i]=0;
	}
}