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

· · 题解

提供另一个视角，维护一个栈 S，维护目前所有确定在答案中，且存在相邻点尚未确定的点，每次确定答案位置下一位的时候（假设填 x）时 x 与 S 有连边的点必然构成了 S 的一个栈顶前缀，然后把一些度数变成 0 的点扔掉，最后把 x push 进去（如果度数不为 0 的话）。

树是简单的，你任意顺序重排儿子后把自己随便插进去就好。

接下来不妨假设图连通（否则可以简单合并），把圆方树建出来，类比树的情况，先考虑仙人掌，圆点随便重排完把自己插进去，方点就正着或者倒着遍历一下子节点就好了，将一般图归约到仙人掌是经典问题，\mathcal{O}(n\log n)。