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

· · 题解

简单好写做法！

快进到给定点双怎么求哈密顿回路，其他部分可以看其他题解。

结论：

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

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

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

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

一些对第 4 条结论的说明：

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

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

代码，用了链表维护字典序。