题解：CF1656I Neighbour Ordering

· · 题解

好牛的题/se

首先显然可以拆开每个 scc 考虑。

首先发现，一个 K_4 同构的子图是无解的。这启发我们用点广义串并联技巧。

但是你再发现，下面这种东西也是无解的，就成为核仁图：

然后你大概手搓一下这种东西，就能发现其构型肯定有个哈密顿圈，圈上有些不相交的边。

大概长这样。

然后构造是简单的，只要把每个点的边顺时针排序即可。

问题是怎么找出每个 scc 的哈密顿圈。考虑上面的广义串并联图技巧，但是根据上面核仁图的反例，我们大概是不能缩重边的。于是我们只需要去缩二度点。

考虑一个二度点 u，有个 (u,x),(u,y)。那么我们删掉 u，加上 (x,y)。那么在剩下的图构造完之后，我们把 u 插入到 (x,y) 之间即可。

其实这里也不需要递归，我们只需要倒过来相当于每次加入一个点 u 即可。

可以证明，合法的图都能通过这种方式构造。只需要判断每次加入一个点 u 时，x,y 是否相邻。用链表维护一下就行。