现在有这样一个问题:
给定一个无向图,多次询问 (x,y),输出是否存在一条 1→x→y 或 1→y→x 的简单路径。
题解里面说,存在这样的简单路径当且仅当满足下列条件之一:
- 在以 1 为根的
dfs树
上, x,y 有祖先关系;
- x 或者 y 与 lca(x,y) 在同一个点双连通分量里。
但我感觉好像并不存在第二种情况,但是不考虑第二种情况就 WA 了,请问能不能举出一例?
换句话说,能不能举出一例无向图和一对点 (x,y) ,满足存在一条 1→x→y 或 1→y→x 的简单路径,且在某一棵 dfs树
上 x,y 没有祖先关系?