题意
给定一张 (n) 个点 (m) 条边的无向图，问删去每个点后，原图是不是二分图。输出一个长度为 (n) 的 ( ext{01}) 串表示答案。
多组数据。
(Tle 5,space 1le n,mle 10^5,space 1le u,vle n,space u≠v)
题解
不难发现，一个没有奇环（奇数条边的环）的图就是二分图。
考虑分治，若一个分治区间外的点已经连出了奇环，那删掉这个区间的每个点的答案都是 (0)。若分治到区间长度为 (1) 时，这个区间外的点还没连出奇环，那删掉这个点的答案就是 (1)。
可以用并查集检测奇环，但由于分治回溯时需要撤销连边，不能路径压缩，所以用按秩合并的并查集。注意按照大小合并，按深度合并会 TLE。
考虑如何判断新加的一条边的两端点是否颜色相同（即是否连出奇环）。
初始时设每个点的颜色为 (0)（也可以为 (1)，这里为了让接下来的操作方便理解，就设成 (0)）。不难发现当两个并查集合并时，连接这两个并查集的边的两端点的颜色可能相同，这时我们最简单的解决方式是 把小的并查集的所有点的颜色都反转。
但是我们显然不能暴力扫一遍子树，这样复杂度是错的。
回想一下，我们按秩合并的并查集的深度是不是 (log) 的？
那我们求一个点的颜色时，只需要从这个点往根扫一遍就行了吧？
所以我们只需要修改小的并查集的根节点颜色。具体地，并查集的每个点维护一个 ( ext{01}) 标记，( ext{0}) 表示以该点为根的子树不翻转颜色，( ext{1}) 表示以该点为根的子树翻转颜色。一个点的颜色就是 该点 到 其所在的并查集的根节点 上所有点颜色的异或和。
一个细节：边一定都是从小分治区间的点 往大分治区间的点连。
#include<bits/stdc++.h>
#define N 100010
using namespace std;
inline int read(){
int x=0; bool f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
if(f) return x;
return 0-x;
}
int n,m,col[N],fa[N],siz[N];
char ans[N];
struct edge{int v,nxt;}e[N<<1];
int hd[N],cnt;
inline void add(int u, int v){e[++cnt]=(edge){v,hd[u]}, hd[u]=cnt;}
struct DSU{int u,v,col_u,col_v,siz_u,siz_v;}stk[N],tmp;
int top;
inline void init(){
top=cnt=0;
ans[n+1]=0;
for(int i=1; i<=n; ++i) hd[i]=col[i]=0, siz[i]=1, fa[i]=i;
}
int find_fa(int x){
return fa[x]==x ? x : find_fa(fa[x]);
}
int find_col(int x){
if(fa[x]==x) return col[x]; //显然根的col为0
return find_col(fa[x])^col[x];
}
int merge(int u, int v){
int fa_u=find_fa(u), fa_v=find_fa(v);
int col_u=find_col(u), col_v=find_col(v);
//cout<<u<<' '<<v<<' '<<fa_u<<' '<<fa_v<<' '<<col_u<<' '<<col_v<<endl;
if(fa_u==fa_v){
if(col_u==col_v) return 0;
return 1;
}
int rt,son;
if(siz[fa_u]<siz[fa_v]) rt=fa_v, son=fa_u;
else rt=fa_u, son=fa_v;
//cout<<rt<<endl;
stk[++top] = (DSU){rt,son,col[rt],col[son],siz[rt],siz[son]};
if(col_u==col_v) col[son]^=1;
fa[son]=rt, siz[rt]+=siz[son];
return 1;
}
void undo(int pre){
//printf("undo
");
while(top>pre){
tmp=stk[top--];
int u=tmp.u, v=tmp.v;
col[u]=tmp.col_u, col[v]=tmp.col_v;
fa[u]=u, fa[v]=v;
siz[u]=tmp.siz_u, siz[v]=tmp.siz_v;
}
}
int unite(int l, int r, int a, int b){
//printf("unite
");
for(int j=l; j<=r; ++j)
for(int i=hd[j]; i; i=e[i].nxt){
if(a<=e[i].v && e[i].v<=b) continue;
if(!merge(j,e[i].v)) return 0;
}
return 1;
}
void cdq(int l, int r, bool flag){
//printf("cdq:%d %d %d
",l,r,flag);
if(l==r){ans[l]=flag+'0'; return;}
int mid=l+r>>1;
if(!flag){
cdq(l,mid,0), cdq(mid+1,r,0);
return;
}
int pre=top; bool now=unite(mid+1,r,l,mid);
cdq(l,mid,now), undo(pre);
now = unite(l,mid,mid+1,r);
cdq(mid+1,r,now), undo(pre);
}
int main(){
int T=read();
while(T--){
n=read(), m=read();
init();
int u,v;
for(int i=1; i<=m; ++i) u=read(), v=read(), add(u,v), add(v,u);
cdq(1,n,1);
printf("%s
",ans+1);
}
return 0;
}