「bzoj4424」「Codeforces19E」Fairy - CDQ分治左右逼近

题目大意

给定$n$个点，$m$条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。

---

题目分析

有关$O(n)$的做法可以见这里->传送门
在这里主要谈一谈CDQ分治的做法。
还记得之前有一道题叫做消失之物吗？

我们也可以用CDQ分治左右逼近的做法解决这道题。
缺一个物品的问题几乎都可以用CDQ分治解决，当然必须要满足CDQ分治的条件。
我们还是同样先处理后边对左边的影响，递归左子区间，消除影响再递归右子区间。

我们可以在处理影响的时候加边，在消除影响的时候删边，在递归到单位区间时判断是否是二分图。
不难发现，这样的算法是$O(n^2)$的，写的不好可能到达$O(n^2logn)$，这对于暴力是没有优势的。

主要的瓶颈在于我们每次递归到单位区间要重新求一次二分图，而且删除影响不好处理。
注意到CDQ分治到达单位区间时一般都是$O(1)$返回，有没有一种方法可以快速的删边加边并判定二分图呢？

这样的数据结构是有的，它就是带权可持久化并查集 或 LCT（此处略）。
我们用并查集维护连通集合，加入一条边就合并集合。
并查集维护一个信息表示该点向上的集合中有多少条边，那么每加入一条边如果构成环我们就能知道它是奇环还是偶环。

当然这道题因为CDQ分治降低了加减边的规模，因此我们可以在每次分治执行 $O(R-L+1)$ 的操作，那么就不需要用主席树维护并查集，直接用栈保存并查集的历史信息即可。

另外，因为我们维护的信息的特殊性，不能使用路径压缩，为了加快并查集的时间效率，我们可以采用按秩合并的方法。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
bool bj=0,Dist[1000005];
struct Edge {
	int from,to;
} edge[1000005];
int n,m,father[1000005],depth[1000005],top=0,ans=0,Ans[1000005];
struct St {
	int x,y,hx,hy;
} S[1000005];
int Get_Father(int x) {
	if(father[x]==x)return x;
	else return Get_Father(father[x]);
}
int Get_Dist(int x) {
	if(father[x]==x)return 0;
	else return Get_Dist(father[x])^Dist[x];
}
void Merge(int id) {
	if(bj)return;
	Edge& e=edge[id];
	int fx=Get_Father(e.from),fy=Get_Father(e.to),dx=Get_Dist(e.from),dy=Get_Dist(e.to);
	if(fx==fy) {
		if(dx==dy)bj=1; //找到奇环 
		return;
	}
	if(depth[fx]<depth[fy])swap(fx,fy);
	S[++top]= (St) {
		fx,fy,depth[fx],depth[fy]
	};
	father[fy]=fx;
	Dist[fy]=1^dx^dy;
	if(depth[fx]==depth[fy])depth[fx]++;
}
void Cut(int id) {
	father[S[id].x]=S[id].x;
	depth[S[id].x]=S[id].hx;
	Dist[S[id].x]=0;
	father[S[id].y]=S[id].y;
	depth[S[id].y]=S[id].hy;
	Dist[S[id].y]=0;
}
void CDQBinary(int Left,int Right) {
	if(Left==Right) {
		if(!bj)Ans[++ans]=Left;
		return;
	}
	int mid=(Left+Right)>>1,tmptop=top,tmpbj=bj;
	for(int i=mid+1; i<=Right; i++)Merge(i);
	if(!bj)CDQBinary(Left,mid);
	bj=tmpbj;
	while(top>tmptop) {
		Cut(top);
		top--;
	}
	for(int i=Left; i<=mid; i++)Merge(i);
	if(!bj)CDQBinary(mid+1,Right);
	bj=tmpbj;
	while(top>tmptop) {
		Cut(top);
		top--;
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	if(m==0) {
		puts("0");
		return 0;
	}
	for(int i=1; i<=m; i++) {
		edge[i].from=Get_Int();
		edge[i].to=Get_Int();
	}
	for(int i=1; i<=n; i++) {
		father[i]=i;
		depth[i]=1;
	}
	CDQBinary(1,m);
	printf("%d\n",ans);
	for(int i=1; i<=ans; i++)printf("%d%c",Ans[i],i==ans?'\n':' ');
	return 0;
}