题目
一个n个点m条边的无向图，每个点有0 / 1 的标号;
有q个询问，每次询问(u,v)直接是否存在回文路径（可以经过重复的点和边）;
$1 \le n \le 5 \times 10^3 \ , \ 1 \le m \le 5 \times 10^5 \ , \ 1 \le q \le 10^5 $
题解
-
Part 1
- n较小，直接预处理所有点对的答案，\(f_{u,v}\)表示 \(u\) 和 \(v\) 是否有 回文路径;
- 初始化所有点和所有同色边，枚举转移到的点\(u’\)和\(v’\) ,时间复杂度：\(O(m^2)\) ;
-
Part 2
- 暴力算法没有很好的利用01的性质;
- 可以发现每次的扩展是对称的，将边分成同色边和异色边;
- 对于异色边形成的连通块，一定是二分图，在二分图中两个点中间路径的奇偶性一定是确定的。图连通，扩展时奇偶性也不会改变，同时直接来回走一条边形成的字符是一样的，所以只需要保留二分图的一个生成树即可;
- 对于同色边形成的连通块，如果是二分图同理，否则一定可以走到奇环上去交换奇偶性，那么先做一个生成树，再随便在某个点上加入一个奇环代替也是一样的;
- 时间复杂度：\(O(n^2)\) ;
#include<bits/stdc++.h>
#define mk make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=5010;
int n,m,Q,o,hd[N],fg,col[N],head=1,tail,f[N][N];
typedef pair<int,int>pii;
pii q[N*N];
vector<int>g[N];
char s[N];
struct Edge{int v,nt;}E[N<<2];
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};hd[u]=o++;
E[o]=(Edge){u,hd[v]};hd[v]=o++;
}
void dfs(int u,int typ){
for(int i=0;i<(int)g[u].size();++i){
int v=g[u][i];
if((s[u]^s[v])!=typ)continue;
if(!~col[v]){col[v]=col[u]^1;adde(u,v);dfs(v,typ);}
else if(col[u]==col[v])fg=1;
}
}
int main(){
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
scanf("%d%d%d%s",&n,&m,&Q,s+1);
for(int i=1;i<=n;++i)hd[i]=-1,q[++tail]=mk(i,i),f[i][i]=1;
for(int i=1;i<=m;++i){
int u,v;scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
if(s[u]^s[v])continue;
f[u][v]=f[v][u]=1;
q[++tail]=mk(u,v);
}
for(int I=0;I<2;++I){
for(int i=1;i<=n;++i)col[i]=-1;
for(int i=1;i<=n;++i)if(!~col[i]){
fg=col[i]=0;dfs(i,I);
if(fg)adde(i,i);
}
}
while(head<=tail){
int u=q[head].fi,v=q[head].se;head++;
for(int i=hd[u];~i;i=E[i].nt)
for(int j=hd[v];~j;j=E[j].nt){
int u1=E[i].v,v1=E[j].v;
if(s[u1]!=s[v1]||f[u1][v1])continue;
q[++tail]=mk(u1,v1);
f[u1][v1]=f[v1][u1]=1;
}
}
for(int i=1;i<=Q;++i){
int u,v;scanf("%d%d",&u,&v);
puts(f[u][v]?"YES":"NO");
}
return 0;
}
