title: 无向图里找奇偶环 - OI回忆录
tag:
- DP
description: https://codeforces.com/gym/103931/problem/J
我退役后打ACM，当时队内每周vp训练，我寻思着调场水一点的就当交作业了，就选了这场。
虽然是单挑，虽然开局不利，但也非常顺呐，一下过了8题。C题久攻不下，I题思路想错，F题谁会去写，于是我看向J题。
看完题，思路啪一下过来了，很快啊。就是答案不大于5，且答案大于2的很好判断，搜一下判断答案小于等于2的就行了。
后来发现在无向图中找奇偶环不会QAQ，也不会找最大的奇环，憋出的绝杀没放出来。
猛然回首自己的OI生涯，发现这种找奇偶环已经不是第一次不会了。。。这道题叫 Just Some Bad Memory ，真的扎心。。。
那时我还是非常菜但远比现在强的初三OIer，有幸能参加在中山纪念中学举办的PKUWC2019。那次的d2t2就是类似的题。。。当时知道结论但是不知道怎么写真是难受，写的时候连连叫苦，最后d2崩盘喜提三等。无论是当时还是现在都没有把那次旅游赛当真毕竟后来拿一等了，但那段与朋友一起的时光令此时高考炸裂远走他乡的我愈发向往。此时的我打ICPC/CCPC比赛不再有初高中时的强力队友带我，更多时候一个队必须由我扛起（marisa化），拿Au更是奢望。
这个算法赛后我想了很久，实际上还是巧妙的。
网上有说，是统计边双连通分量同时二分图染色求奇环，然后取数一个连通分量里边数和点数是否对应来判断是否有奇偶环（假如不是简单环且整个是奇环则有偶环），我说你这个不行。类似“8”形的两个奇环，中间连个割点，形成不了一个偶环。
我说我这个可以。先用dfs黑白染色求出是否有奇环。假如两个奇环有公共边，则去掉公共边就成了一个偶环。如果没有偶环，则整个图应该是仙人掌森林。这样一来，找最大奇环也同时解决了，因为仙人掌不会有重叠的环；假如不是仙人掌，两个奇环重叠，且较大的奇环被较小的奇环给占了边，这样就有偶环，这道题已经解决了。
于是考虑如何找两个奇环的公共边。其实只要判断是不是仙人掌就可以了呀。考虑一个奇环，将它上面的边做标记，被标记的边经过两次就重了，立即退出，每条边被扫一至两次，时间复杂度是 $ \mathcal{O}(m) $ 的。考虑dfs，只有回溯祖先节点的边可以成环，直接在栈里标记就行。
My Code
但这种手法有些笨拙，可以直接树上差分。
My Code
可能这个更笨拙？