问一个图连通性的问题
  • 板块学术版
  • 楼主ZigZagKmp
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/3/22 20:17
  • 上次更新2023/11/5 01:43:48
查看原帖
问一个图连通性的问题
35871
ZigZagKmp楼主2021/3/22 20:17

现在有这样一个问题:

给定一个无向图,多次询问 (x,y)(x,y),输出是否存在一条 1xy1\rightarrow x\rightarrow y1yx1\rightarrow y\rightarrow x简单路径。

题解里面说,存在这样的简单路径当且仅当满足下列条件之一:

  1. 在以 11 为根的dfs树上, x,yx,y 有祖先关系;
  2. xx 或者 yylca(x,y)\mathrm{lca}(x,y) 在同一个点双连通分量里。

但我感觉好像并不存在第二种情况,但是不考虑第二种情况就 WA 了,请问能不能举出一例?

换句话说,能不能举出一例无向图和一对点 (x,y)(x,y) ,满足存在一条 1xy1\rightarrow x\rightarrow y1yx1\rightarrow y\rightarrow x简单路径,且在某一棵 dfs树x,yx,y 没有祖先关系?

2021/3/22 20:17
加载中...