题目大意
给你一张\(n\)个点\(m\)条边的无向图，问删去每个点后，原图是不是二分图。
\(n,m\leq 100000\)
题解
一个图是二分图\(\Longleftrightarrow\)该图不存在奇环
可以用并查集，维护每个点到根的距离
如果删除\(x\)点，就要把所有不与\(x\)连接的边加入并查集
考虑分治，对于区间\([l,r]\)，我们先把与\([l,mid]\)链接且不与\([mid+1,r]\)链接的边加入并查集，然后递归处理\([mid+1,r]\)。另一边的情况类似。
因为有撤销操作，所以要用按秩合并的并查集
时间复杂度：\(O(m\log^2 n)\)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct list
{
int v[200010];
int t[200010];
int h[100010];
int n;
void clear()
{
memset(h,0,sizeof h);
n=0;
}
void add(int x,int y)
{
n++;
v[n]=y;
t[n]=h[x];
h[x]=n;
}
};
list li;
int f[100010];
int s[100010];
int d[100010];
int find(int x)
{
return f[x]==x?x:find(f[x]);
}
int getdist(int x)
{
return f[x]==x?0:getdist(f[x])^d[x];
}
int e1[100010];
int e2[100010];
int top;
int ans[100010];
int merge(int x,int y)
{
int dist=getdist(x)^getdist(y)^1;
if((x=find(x))==(y=find(y)))
return dist;
top++;
if(s[x]<=s[y])
{
e1[++top]=x;
e2[top]=y;
d[x]=dist;
s[y]+=s[x];
f[x]=y;
}
else
{
e1[++top]=y;
e2[top]=x;
d[y]=dist;
s[x]+=s[y];
f[y]=x;
}
return 0;
}
void solve(int l,int r)
{
if(l==r)
{
ans[l]=1;
return;
}
int mid=(l+r)>>1;
int now=top;
int i,j;
int b=1;
for(i=l;i<=mid&&b;i++)
for(j=li.h[i];j&&b;j=li.t[j])
if(li.v[j]<=mid||li.v[j]>r)
b^=merge(i,li.v[j]);
if(b)
solve(mid+1,r);
else
for(i=mid+1;i<=r;i++)
ans[i]=0;
while(top>now)
{
f[e1[top]]=e1[top];
s[e2[top]]-=s[e1[top]];
top--;
}
now=top;
b=1;
for(i=mid+1;i<=r&&b;i++)
for(j=li.h[i];j&&b;j=li.t[j])
if(li.v[j]<l||li.v[j]>mid)
b^=merge(i,li.v[j]);
if(b)
solve(l,mid);
else
for(i=l;i<=mid;i++)
ans[i]=0;
while(top>now)
{
f[e1[top]]=e1[top];
s[e2[top]]-=s[e1[top]];
top--;
}
}
void solve()
{
top=0;
int n,m;
scanf("%d%d",&n,&m);
int i;
int x,y;
li.clear();
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
li.add(x,y);
li.add(y,x);
}
for(i=1;i<=n;i++)
{
f[i]=i;
s[i]=1;
}
solve(1,n);
for(i=1;i<=n;i++)
putchar(ans[i]+'0');
putchar('\n');
}
int main()
{
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}