题解：P11832 [省选联考 2025] 图排列

一个点双有唯一的哈密顿回路。

对于一条边，如果原图删掉这条边后点双连通性不变，就可以直接删掉，不影响哈密顿回路。

建立 dfs 生成树。注意到只要保留 $low$ 边和树边，其他边去掉不影响点双连通性。$low$ 边指的是子树终点最浅的返祖边，如果有多个只要保留起点最深的。

考虑一个点 $u$ ，如果子树内有两条边到祖先，就把 $u$ 到父亲的边删掉。剩下的边形成哈密顿回路。

只要从原图删掉一条边后点双连通性不变，就能把这条边删掉，所以删完的图还是双连通的。

（只保留 $low$ 边后）如果有个点 $u$ 满足子树内有 $\ge 3$ 条边到祖先，就无解了。由此可得，每个点只有 $\le 2$ 个儿子。

$low$ 边总是不会被删。这是因为，假设删了 $(u,v)$ ，其中 $v$ 是 $u$ 的祖先，则 $u$ 到 $v$ 路径上肯定有至少一个点只被 $(u,v)$ 覆盖，这个点就会变成割点。