建任意生成树,对非树边导出的奇环(设有 $k$ 个这样的非树边),在树上路径做覆盖,如果存在一个点被覆盖了 $k$ 次,则删除这个点后不存在奇环。否则即有两个奇环的点集不交,不可能删除一个点后成为二分图。
by 小粉兔 @ 2024-02-27 15:03:04
@[小粉兔](/user/10703) 感谢
by 小超手123 @ 2024-02-27 15:08:51
补充一下,被删点不能同时被偶环和奇环(由一条返祖边组成)跨越
具体证明见https://www.luogu.com.cn/problem/AT_joisc2014_j
by zuishuai @ 2024-02-27 16:33:56
@[zuishuai](/user/515001) 怪不得我代码写出来过不了
by 小超手123 @ 2024-02-27 16:39:58
@[zuishuai](/user/515001) 删点没有问题吧
by 0x824EE @ 2024-02-28 07:51:03
已经深刻认识到自己的错误,并深刻反省 @[zuishuai](/user/515001)
by 0x824EE @ 2024-02-28 14:46:19