P5292 [HNOI2019] 校园旅行

比较不错的图论题。

考虑一个暴力算法，设 $f(i,j)$ 表示 $i,j$ 之间是否存在回文路径。那么我们同时枚举包含端点 $i,j$ 的边，再向外扩展。这样做时间复杂度为 $\mathcal O(m^2)$ 的。但如果单次只枚举一条边的话可以做到 $\mathcal O(nm)$。

其实一个关键条件是答案可以不为简单路径。那么我们可以反复地走一条边以达到回文。最终路径由 $01(10),00,11$ 组成。那么我们只需要满足，这样的每一段都可以在不改变奇偶行的条件下进行扩展。

我们需要满足两边需要扩展的同色边奇偶性相同。奇偶性相同容易考虑二分图也具有这样的性质。我们将边分为同色和异色两类。我们还是按照暴力算法进行扩展，扩展的两条边显然应当属于同一类。我们分别考虑两类边：

同色：将所有同色边连起来，判断得到的是否是二分图。如果是的话，我们只用保留其生成树，这样不会产生影响，然后直接扩展；如果不是的话那么说明必定存在奇环，我们可以通过绕奇环来改变奇偶性，于是在其生成树上任意一个点加一个自环就可以了。
异色：显然得到的一定是二分图，只用保留其生成树，然后直接扩展。

这样我们边数就变为 $\mathcal O(n)$ 的了。最终时间复杂度为 $\mathcal O(n^2+m)$。

Code

#include<iostream>
#include<cstdio>
#include<queue>
#define fi first
#define se second
using namespace std;
using PII=pair<int,int>;
const int N=5e3+10,M=5e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Gragh
{
    int tot,head[N],ver[M<<1],ne[M<<1];
    void add(int u,int v)
    {
        ver[++tot]=v;
        ne[tot]=head[u];
        head[u]=tot;
    }
}e,g;
int n,m,q;
int a[N];
int fa[N];
int flag,vis[N];
bool ans[N][N];
queue<PII>Q;
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void merge(int x,int y){x=get(x),y=get(y),fa[x]=y;}
void dfs(int x,int col)
{
    vis[x]=col;
    int z=3-col;
    for(int i=e.head[x];i;i=e.ne[i])
    {
        int y=e.ver[i];
        if(!vis[y])
        {
            dfs(y,z);
            g.add(x,y),g.add(y,x);
            ans[x][y]=ans[y][x]=1;
            Q.push({x,y});
        }
        else if(vis[y]!=z)flag=1;
    }
}
int main()
{
    read(n,m,q);
    for(int i=1;i<=n;i++)scanf("%1d",&a[i]),fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u,v);
        if(a[u]==a[v])e.add(u,v),e.add(v,u);
        else if(get(u)!=get(v))g.add(u,v),g.add(v,u),merge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            flag=0;
            dfs(i,1);
            if(flag)g.add(i,i);
        }
    for(int i=1;i<=n;i++)ans[i][i]=1,Q.push({i,i});
    while(!Q.empty())
    {
        int x=Q.front().fi,y=Q.front().se;
        Q.pop();
        for(int i=g.head[x];i;i=g.ne[i])
            for(int j=g.head[y];j;j=g.ne[j])
            {
                int u=g.ver[i],v=g.ver[j];
                if(!ans[u][v]&&a[u]==a[v])ans[u][v]=ans[v][u]=1,Q.push({u,v});
            }
    }
    while(q--)
    {
        int u,v;
        read(u,v);
        puts(ans[u][v]?"YES":"NO");
    }
    return 0;
}