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

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

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

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