题目

一个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
        
         #define mk make_pair#define fi first #define se second #define pb push_backusing namespace std;const int N=5010;int n,m,Q,o,hd[N],fg,col[N],head=1,tail,f[N][N];typedef pair
         
          pii;pii q[N*N];vector
          
           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;}