题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5354
题意：给你n个点m条边，问对于每一个点，删去它之后的图是否是二分图。（ 1<=n,m<=105 ）
思路：这题的代码是看了南神的博客之后才懂得，代码也参考了他的代码。南神的题解
因为要判断每一个点，而且一旦一个点之外的几个点形成了奇环的话这个点一定就是No，所以用分治来解。先判断每一段之外的点是否会成为奇环，如果是的话，这一段就全是No，反之就把这些点放到并查集里并记录，然后分治当前段，直到分治进行到单个点，分治结束后把并查集还原。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; #define MS(x,y) memset(x,y,sizeof(x)) #define MP(x,y) make_pair(x,y) #define lowbit(x) (x&(-x)) typedef long long LL; typedef pair<int,int> P; inline void fre1(){freopen("input.txt","r",stdin);/*freopen("output.txt","w",stdout);*/} inline void fre2(){fclose(stdin);/*fclose(stdout);*/} const int MAXN=1e5+5; const double EPS=1e-8; vector<P> vec[MAXN<<2]; int col[MAXN],siz[MAXN],f[MAXN],ans[MAXN]; int n,m; inline bool isin(int a,int l,int r){ return l<=a&&a<=r; } void process(int l,int r,int rt,vector<P> &V); P findfa(int x){ int ret=x,w=0; for(;ret!=f[ret];ret=f[ret]) w^=col[ret]; w^=col[ret]; return MP(ret,w); } void solve(int l,int r,int rt){ if(l==r){ ans[l]=1; return ; } int m=(l+r)>>1; vec[rt<<1].clear(); vec[rt<<1|1].clear(); vector<P> tp[2]; int len=vec[rt].size(); for(int i=0;i<len;++i){ int u=vec[rt][i].first,v=vec[rt][i].second; if(isin(u,l,m)||isin(v,l,m)) vec[rt<<1].push_back(vec[rt][i]); else tp[0].push_back(vec[rt][i]); if(isin(u,m+1,r)||isin(v,m+1,r)) vec[rt<<1|1].push_back(vec[rt][i]); else tp[1].push_back(vec[rt][i]); } process(l,m,rt<<1,tp[0]); process(m+1,r,rt<<1|1,tp[1]); } void process(int l,int r,int rt,vector<P> &V){ P fu,fv; vector<P> ret; int len=V.size(); bool flag=false; for(int i=0;i<len;++i){ int u=V[i].first,v=V[i].second; fu=findfa(u); fv=findfa(v); if(fu.first==fv.first){ if(fu.second==fv.second){ flag=true; break; } } else{ int t1=fu.first,t2=fv.first; if(siz[t1]<siz[t2]) swap(t1,t2); int t3=fu.second^fv.second; f[t2]=t1; siz[t1]+=siz[t2]; col[t2]^=t3; ret.push_back(MP(t2,t3)); } } if(flag){ for(int i=l;i<=r;++i) ans[i]=0; } else solve(l,r,rt); for(int i=ret.size()-1;i>=0;--i){ int u=ret[i].first; siz[f[u]]-=siz[u]; f[u]=u; col[u]^=ret[i].second; } } int main() { int T,u,v; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) col[i]=1,siz[i]=1,f[i]=i; vec[1].clear(); for(int i=0;i<m;++i){ scanf("%d%d",&u,&v); if(u>v) swap(u,v); vec[1].push_back(MP(u,v)); } solve(1,n,1); for(int i=1;i<=n;++i) putchar(ans[i]+'0'); putchar(10); } return 0; }