HACK
查看原帖
HACK
399150
ShunpowerSHUN理成张楼主2024/8/7 20:48

有一个流传较广的边双做法,可以通过这题的赛时数据。

然而,这是错的。异色边导出子图的 DFS 树上,同色边 (u,v)(u,v) 的 LCA 的父亲与其中一个点(比如 u)u) 边双连通时,并不能保证 0→u→v0\to u\to v 的路径是简单路径,因为边双连通无法保证不经过树上 u→vu\to v 路径中的点。

例如下面这个例子(所有编号均加 11):

颜色没怎么用对,只有 (7,9)(7,9) 是同色边。显然 77 与 22 边双连通,但不存在不经过 (7,9)(7,9) 的 1→7→91\to 7\to 9 简单路径。

数据:

in:
1
9 11
LHLHLHLHL
0 1
1 2
2 3
3 4
4 5
5 6
2 7
7 8
0 3
3 6
6 8

ans:
no
2024/8/7 20:48
加载中...