fzyzojP3412 -- [校内训练20171212]奇数

墨蓝 2021-12-23 14:59 186阅读 0赞

![1399631-20190202232021270-155891369.png][]

![1399631-20190202232033840-1050268105.png][]

套路地，

考虑dfs树上搞事情

容易发现，对于(x,y)如果dfs树上距离为奇数，或者dfs树上路径中有一条边在某个简单奇环上，那么可以经过奇数条边到达

判断边在某个奇环上：

点双，点双中黑白染色，如果有一个奇环，那么点双中的所有边都在一个奇环中

询问

倍增预处理，LCA搞一下即可

#include<bits/stdc++.h>
    #define il inline
    #define reg register int
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    il void rd(int &x){
        char ch;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    namespace Miracle{
    const int N=500000+5;
    int n,m;
    struct node{
        int nxt,to;
        int id;
    }e[2*N];
    int a[N][2];
    int hd[N],cnt=1;
    int ok[N],dep[N];
    int fa[N][20],has[N][20];
    int blo[N],bls;
    void add(int x,int y,int d){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        e[cnt].id=d;
        hd[x]=cnt;
    }
    int dfn[N],low[N];
    int df;
    int be[N];
    int dcc;
    vector<int>mem[N];
    int exi[N];//dcc exi a jihuan
    
    int sta[N],top;
    int ge[N];
    int rt;
    void tarjan(int x){
    //    cout<<" tarjan "<<x<<endl;
        dfn[x]=low[x]=++df;
        sta[++top]=x;
        blo[x]=bls;
        bool fl=false;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(!dfn[y]){
                tarjan(y);
                low[x]=min(low[x],low[y]);
                if(low[y]>=dfn[x]){
                    if(fl||x!=rt) ge[x]=1;
                    fl=true;
                    ++dcc;
                    mem[dcc].push_back(x);
                    int z;
                    do{
                        z=sta[top--];
                        mem[dcc].push_back(z);
                    }while(z!=y);
                }
            }else low[x]=min(low[x],dfn[y]);
        }
    }
    int co[N];//white(2) or black(1) or blank(0)
    int bian[2*N],num;
    bool fl;
    void dfs1(int x,int c,int col){
        co[x]=col;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(be[y]!=be[x]) continue;
            bian[++num]=e[i].id;
            if(!co[y]){
                dfs1(y,c,col^1);
            }else{
                if(co[y]==co[x]){
                    fl=false;
                }
            }
        }
    }
    bool vis[N];
    void dfs2(int x,int d){
        dep[x]=d;
        vis[x]=1;
    //    cout<<" dfs2 "<<x<<" "<<d<<endl; 
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(vis[y]) continue;
            fa[y][0]=x;
            has[y][0]=ok[e[i].id];
            dfs2(y,d+1);
        }
    }
    bool wrk(int x,int y){
        int lp=0;
        int tmp=dep[x]+dep[y];
        if(dep[x]<dep[y]) swap(x,y);
        for(reg j=19;j>=0;--j){
            if(dep[fa[x][j]]>=dep[y]){
                lp|=has[x][j];
                x=fa[x][j];    
            }
        }
        if(x==y) {
            if((tmp-2*dep[x])%2==1) return true;
            if(lp) return true;
            return false;
        }
        for(reg j=19;j>=0;--j){
            if(fa[x][j]!=fa[y][j]){
                lp|=has[x][j];
                lp|=has[y][j];
                x=fa[x][j];y=fa[y][j];
            }
        }
        lp|=has[x][0]|has[y][0];
        x=fa[x][0];
        
        if((tmp-2*dep[x])%2==1) return true;
        if(lp) return true;
        return false;
    }
    int main(){
        rd(n);rd(m);
        int x,y;
        for(reg i=1;i<=m;++i){
            rd(x);rd(y);
            a[i][0]=x;a[i][1]=y;
            add(x,y,i);add(y,x,i);
        }
        for(reg i=1;i<=n;++i){
            if(!dfn[i]){
                top=0;
                ++bls;
                rt=i;
                tarjan(i);
            }
        }
        //cout<<" dcc "<<dcc<<endl;
        for(reg i=1;i<=dcc;++i){
        //    cout<<" nunumumuun "<<i<<endl;
            for(reg j=0;j<(int)mem[i].size();++j){
            //    cout<<mem[i][j]<<endl; 
                be[mem[i][j]]=i;
                co[mem[i][j]]=0;
            }
            num=0;
            fl=true;
            dfs1(mem[i][0],i,1);
            if(!fl){
                for(reg j=1;j<=num;++j){
            //        cout<<" bian[i] "<<bian[j]<<endl;
                    ok[bian[j]]=1;
                }
            }
        }
        memset(dfn,0,sizeof dfn);
        for(reg i=1;i<=n;++i){
            if(!vis[i]){
                dfs2(i,1);
            }
        }
        for(reg j=1;j<=19;++j){
            for(reg i=1;i<=n;++i){
                fa[i][j]=fa[fa[i][j-1]][j-1];
                has[i][j]=has[i][j-1]|has[fa[i][j-1]][j-1];
            }
        }
        int q;
        rd(q);
        while(q--){
            rd(x);rd(y);
            if(blo[x]!=blo[y]){
                puts("No");
            }
            else puts(wrk(x,y)?"Yes":"No");
        }    
        return 0;
    }
    
    }
    signed main(){
    //    freopen("data3412.in","r",stdin);
    //    freopen("data3412.out","w",stdout);
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/2/2 13:27:37
    */

转载于:https://www.cnblogs.com/Miracevin/p/10349449.html

[1399631-20190202232021270-155891369.png]: /images/20211223/1f2f4c6c5a4140ecb052b0a299697c01.png
[1399631-20190202232033840-1050268105.png]: /images/20211223/a67c29cbdbfa4a959e2be599475a437b.png