先讨论没有 shift 模式的情况,显然原图是一张半欧拉图才可满足情况。
对于 mode shift 分析后,发现此模式可以完整地删完一张菊花图。
这样只要原图能分成一张半欧拉图 (G) 和一张菊花图 (G') 就有解。
一条枚举的思路就有了。
枚举每一个节点,设其为菊花图的中心 (p) ,对于每一个度数为奇数且与 (p) 点相连的点,贪心地加入菊花图中。
但是我们还需要调整另一些边以应付不同的情况,即将一条边从 (G) 移到 (G') 或从 (G') 移到 (G) 中。
列出一些性质:
-
半欧拉图中有 0 或 2 个奇度节点。
-
菊花图的中心点 (p) 必定位于这条欧拉通路的最终节点。
-
若有两个奇度顶点,欧拉通路的两端点必为这两个奇度顶点。
每次调整都会将 (G) 中的奇度节点加一,这将成为路径的一个起点,而终点必定是 (p) ,所以不可能同时存在两条与 (p) 相连的边同时被调整。
按照上述操作直接模拟即可。
时间复杂度 (mathcal{O}((n+m)^2 log n)) 。
Code(C++):Link.