zcmimi's blog
查看原题

点击跳转

定义

二分图又称作二部图,是图论中的一种特殊模型。

G=(V,E)是一个无向图,

如果顶点V可分割为两个互不相交的子集(A,B),

并且图中的每条边i\leftrightarrow j所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),

则称图G为一个二分图。

简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

判断

区别二分图,关键是看点集是否能分成两个独立的点集。

无向图G为二分图的充分必要条件是: G至少有两个顶点,且其所有回路的长度均为偶数。

证明:

必要性:

G=<V,E>为一个简单无向图,G为二分图,那么可以将V分为V_1,V_2

CG中长度为l的圈,C=(v_1,v_2,...v_{l-1},v_l,v_1)

那么v_1\in V_1,v_2\in V_2,v_3\in V_1 ,\cdots,v_l \in V_2

也就是:

v_1,v_3,v_5,\cdots v_l-1 \in V_1 \\ v_2,v_4,v_6,\cdots v_l \in V_2

所以l必定为偶数

充分性:

设无向图G中每个圈的长度都是偶数,并且假定G为连通图

定义V的两个子集V_1,V_2:

任取v\in V,

V_1=\left\{v|dist(v_i,v) \mod 2 = 0\right\}

V_2=\left\{v|dist(v_i,v) \mod 2 = 1\right\}

V_1的节点间无边连接,

假若不然,设有边v_i\leftrightarrow v_j\in Ev_i,v_j\in V_1,那么vv_i以及vv_j的长> 度都是偶数,

那么vv_iv_jv这个圈的长度为奇数,与给定条件矛盾,所以边v_i\leftrightarrow v_j不存在

同理可证V_2的节点间无边连接

回归正题,我们要判断是否是二分图,只需要判断图里是否存在奇环就可以了

解法一

link-cut tree

考虑到每条边最后都是要删掉的,那么当构成环时,我们就可以将该环中最早要被删掉的边给删去,因为这样一来不会影响连通性,二来又可以化环为链。

添加一条边的时候,若两端未连通,直接连边即可

若两端已经连通,这时一定会形成一个环,为了维护LCT,连接两端时,我们需要把环上消失时刻最早的边给删去,如果是奇环则把这条边加入集合

删边时如果是LCT上的边则断开,在集合中则将其从集合中删除

查询时若集合中没有边,则为二分图

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i(x);i<=y;++i)
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=100011,M=200011,inf=2122219134,P=300011;
int n,m,T,cnt,tot,s[P],fr[P],siz[P],v[P],c[2][P],f[P],ad[N],de[N];
bool rev[P],is[M],on[M];
struct node{int x,y,v;}a[M];
struct edge{int to,nxt;}e[M<<1];
void add(int *head,int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
#define ls c[0][x]
#define rs c[1][x]
void pu(int x){
    s[x]=v[x],fr[x]=x;
    siz[x]=(x>n)+siz[ls]+siz[rs];
    if(s[ls]<s[x])s[x]=s[ls],fr[x]=fr[ls];
    if(s[rs]<s[x])s[x]=s[rs],fr[x]=fr[rs];
}
void pr(int x){rev[x]^=1,ls^=rs,rs^=ls,ls^=rs;}
void pd(int x){
    if(rev[x]){
        if(ls)pr(ls);
        if(rs)pr(rs);
        rev[x]=0;
    }
}
int g(int x){return c[1][f[x]]==x;}
int nrt(int x){return c[0][f[x]]==x||c[1][f[x]]==x;}
void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(nrt(y))c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y);
}
void pda(int x){if(nrt(x))pda(f[x]);pd(x);}
void splay(int x){
    for(pda(x);nrt(x);rotate(x))if(nrt(f[x]))
        rotate(g(x)^g(f[x])?x:f[x]);
    pu(x);
}
void access(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),rs=y,pu(x);
}
void mrt(int x){access(x),splay(x),pr(x);}
int frt(int x){
    for(access(x),splay(x);ls;pd(x),x=ls);
    splay(x);return x;
}
void cut(int x,int y){
    mrt(x);
    if(frt(y)==x&&f[y]==x&&!c[0][y])rs=f[y]=0,pu(x);
}
void inc(int i){
    int x=a[i].x,y=a[i].y;
    if(x==y){is[i]=1,++tot;return;};
    mrt(x);
    if(frt(y)!=x)on[i]=1,mrt(y),f[x]=f[y]=i+n;//直接连接
    else{
        splay(y);
        int k=fr[y]-n;
        if(a[k].v<a[i].v){
            if(siz[y]&1^1)is[k]=1,++tot;//是奇环,将边加入集合
            cut(a[k].x,k+n),cut(a[k].y,k+n);
            mrt(x),mrt(y),f[x]=f[y]=i+n;
            on[k]=0,on[i]=1;
        }
        else if(siz[y]&1^1)is[i]=1,++tot;
    }
}
void dec(int i){
    if(on[i])cut(a[i].x,i+n),cut(a[i].y,i+n);//是LCT上的边
    else if(is[i])--tot;//从集合中删去
}
int main(){
    s[0]=v[0]=inf;
    in(n,m,T);
    fur(i,1,n)v[i]=s[i]=inf,fr[i]=i;
    int x,y,st,ed;
    fur(i,1,m){
        in(x,y,st,ed);
        a[i]={x,y,ed};
        s[i+n]=v[i+n]=ed,fr[i+n]=i+n,siz[i+n]=1;
        add(ad,st,i),add(de,ed,i);
    }
    fur(i,0,T-1){
        for(int j=ad[i];j;j=e[j].nxt)inc(e[j].to);
        for(int j=de[i];j;j=e[j].nxt)dec(e[j].to);
        out(tot?"No\n":"Yes\n");
    }
    flush();
}

解法二

线段树分治+并查集

可以发现每条边存在的时间都是一个区间

如何判断是否出现奇环呢?

并查集维护每个点到根的距离(只需要维护奇偶就可以了)

由于要支持删除,这里使用并查集按秩合并(启发式合并)

连接一条边时,若两端以连通,则判断添加后是否形成奇环

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i(x);i<=y;++i)
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=1000011,M=200011;
int n,m,T,cnt,tp,head[N<<2],f[N],siz[N];
bool ans[N],s[N];
int gf(int x){while(x!=f[x])x=f[x];return x;}
int dis(int x){int d=0;while(x!=f[x])d^=s[x],x=f[x];return d;}
struct node{int x,y;}a[M],sta[N<<2];
struct edge{int to,nxt;}e[N<<2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){add(rt,v);return;}
    int m=l+r>>1;
    if(L<=m)upd(L,R,v,l,m,rt<<1);
    if(R>m)upd(L,R,v,m+1,r,rt<<1|1);
}
void qry(int l,int r,int rt){
    int m=l+r>>1,ff=1,x,y,fx,fy,bg=tp;
    for(int i=head[rt];i;i=e[i].nxt){
        x=a[e[i].to].x,y=a[e[i].to].y,fx=gf(x),fy=gf(y);
        if(fx==fy){if(dis(x)^dis(y)^1){ff=0;break;}}
        else{
            if(siz[fx]>siz[fy])fx^=fy,fy^=fx,fx^=fy;
            siz[fy]+=siz[fx],s[fx]=s[x]^s[y]^1;
            f[fx]=fy;
            sta[++tp]={fx,fy};
        }
    }
    if(ff){
        if(l==r)ans[l]=1;
        else qry(l,m,rt<<1),qry(m+1,r,rt<<1|1);
    }
    while(tp!=bg){
        x=sta[tp].x,y=sta[tp].y;
        siz[y]-=siz[x];
        s[x]=0,f[x]=x;
        --tp;
    }
}
int main(){
    in(n,m,T);
    int st,ed;
    fur(i,1,m){
        in(a[i].x,a[i].y,st,ed);
        if(st<ed)upd(st+1,ed,i,1,T,1);
    }
    fur(i,1,n)f[i]=i,siz[i]=1;
    qry(1,T,1);
    fur(i,1,T)out(ans[i]?"Yes\n":"No\n");
    flush();
}
BZ 4025 二分图
comment评论
Search
search