题目

[HNOI2019]校园旅行

做法

最朴素的做法就是点对扩展\(O(m^2)\)

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

发现\(n\)比较小,我们是否能从\(n\)下手减少边数呢?是肯定的

单独看一个颜色的联通块,如果是二分图,我们生产树和原来的效果相同
如果不是二分图,是会有一个环的,在树上随便圈一个自环和原来的效果相同

而看不同颜色的连边,一定是二分图,再生产树就好了

总边数是\(n\)级的,总复杂度\(O(n^2)\)

Code

#include<bits/stdc++.h>
#include<queue>
typedef int LL;
const LL maxn=5009,maxm=500009;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }
    return x*f;
}
LL f;
LL visit[maxn],col[maxn],a[maxn],fa[maxn];
LL n,m,q,top;
LL mark[maxn][maxn];
struct edge{
    LL u,v;
}e[maxm];
LL Get_fa(LL x){
    return fa[x]==x?x:fa[x]=Get_fa(fa[x]);
}
struct Mp{
    struct node{
        LL to,nxt;
    }dis[maxm<<1];
    LL num;
    LL head[maxn];
    inline void Add(LL u,LL v){
        dis[++num]=(node){v,head[u]}; head[u]=num;
    }
    void Dfs1(LL u,LL c){
        visit[u]=true; col[u]=c;
        for(LL i=head[u];i;i=dis[i].nxt){
            LL v(dis[i].to);
            if(a[v]!=a[u]) continue;
            if(visit[v]){
                if(col[v]==col[u]) f=true;
                continue;
            }
            LL fx(Get_fa(u)),fy(Get_fa(v));
            if(fx!=fy){
                fa[fx]=fy;
                e[++top]=(edge){u,v};
            }
            Dfs1(v,3-c);
        }
    }
    void Dfs2(LL u){
        visit[u]=true;
        for(LL i=head[u];i;i=dis[i].nxt){
            LL v(dis[i].to);
            if(a[v]==a[u] || visit[v]) continue;
            LL fx(Get_fa(u)),fy(Get_fa(v));
            if(fx!=fy){
                e[++top]=(edge){u,v};
                fa[fx]=fy;
            }
            Dfs2(v);
        }
    }
}G1,G2;
std::queue<edge> que;
inline void Build(){
    for(LL i=1;i<=n;++i) fa[i]=i;
    for(LL i=1;i<=n;++i){
        if(!visit[i]){
            f=false;
            G1.Dfs1(i,1);
            if(f) G2.Add(i,i);
        }
    }
    memset(visit,false,sizeof(visit));
    for(LL i=1;i<=n;++i) fa[i]=i;
    for(LL i=1;i<=n;++i)
        if(!visit[i])
            G1.Dfs2(i);
            
    for(LL i=1;i<=top;++i){
        LL u(e[i].u),v(e[i].v);
        G2.Add(u,v); G2.Add(v,u);
    }
    
    for(LL u=1;u<=n;++u){
        que.push((edge){u,u}); mark[u][u]=true;
        for(LL i=G2.head[u];i;i=G2.dis[i].nxt){
            LL v(G2.dis[i].to);
            if(a[v]==a[u]){
                que.push((edge){v,u});
                mark[v][u]=mark[u][v]=true;
            }
        }
    }
    while(que.size()){
        edge tmp(que.front()); que.pop();
        LL u(tmp.u),v(tmp.v);
        for(LL i=G2.head[u];i;i=G2.dis[i].nxt){
            LL v1(G2.dis[i].to);
            for(LL j=G2.head[v];j;j=G2.dis[j].nxt){
                LL v2(G2.dis[j].to);
                if(a[v1]==a[v2]){
                    if(!mark[v1][v2]){
                        mark[v1][v2]=mark[v2][v1]=true;
                        que.push((edge){v1,v2});
                    }
                }
            }
        }
    }
}
char s[maxn];
int main(){
    n=Read(),m=Read(),q=Read();
    scanf(" %s",s+1);
    for(LL i=1;i<=n;++i) a[i]=s[i]-'0';
    while(m--){
        LL u(Read()),v(Read());
        G1.Add(u,v); G1.Add(v,u);
    }
    Build();
    while(q--){
        LL u(Read()),v(Read());
        if(mark[u][v]) puts("YES");
        else puts("NO");
    }
    return 0;
}
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄