Skip to main content

__debug's Home Keep it simple, stupid

[Codeforces 97E] Leaders

Description

给你一个 \(N\) 个点 \(M\) 条边的无向图, 无重边无自环, \(Q\) 次询问, 每次询问点 \(u, v\) 之间是否存在一条长度为奇数的 简单路径.

定义简单路径为不经过重复的 的路径.

\(N, M \le 10^5\)

Solution

怎么无向图的题都这么神啊…

按照套路, 先搞出一个生成树来. 不妨假设整张图是连通的. 以下讨论的路径都是题目中定义的简单路径, 即不经过相同的点的路径

引理 1: 两个 在生成树上的距离为偶数 的点 \(u, v\) 之间存在至少一条长度为奇数的简单路径, 当且仅当这两个点在生成树上的路径上存在至少一条边在某个奇环上.

证明:

先证充分性.

不失一般性, 不妨设路径为 \(u \sim \underline{a_1 \sim b_1} \sim \underline{a_2 \sim b_2} \sim \cdots \sim \underline{a_k \sim b_k} \sim v\). 其中 \(k > 0\), 且 \(\underline{a_i \sim b_i}\) 都在同一段奇环上.

那么奇环的其它部分的长度的奇偶性一定与 \(u \sim v\) 不同, 所以一定存在某一小段与 \(b_i \sim a_{i + 1}\) 的奇偶性不同, 或是连接 \(a_1, b_k\) 的一段与整个 \(a_1 \sim b_k\) 的奇偶性不同.

再证必要性.

还是设路径为 \(u \sim \underline{a_1 \sim b_1} \sim \underline{a_2 \sim b_2} \sim \cdots \sim \underline{a_k \sim b_k} \sim v\).

其中存在一条另路径 \(u \cdots \underline{a_1 \sim b_1} \cdots \underline{a_2 \sim b_2} \cdots \underline{a_k, \sim b_k} \cdots v\), 长度为奇数. (这里 \(k = 0\) 也是可以的)

不妨把 \(u\) 看作 \(b_0\), \(v\) 看作 \(a_{k + 1}\), 那么一定存在一段 \(b_i \cdots a_{i + 1}\) 与 \(b_i \sim a_{i + 1}\) 的奇偶性不同, 这就构成了一个奇环.


所以我们只需要知道每条树边是否在一个奇环上即可. 想到点-双连通分量, 因为不在一个点双中的边显然不会相互影响. (必然经过割点, 不会存在简单环)

首先有一个看起来显然但是并不显然的性质: 两个点在同一个点数大于 \(2\) 的点-双连通分量中, 当且仅当存在至少一个简单环, 这两个点都在环上.

其实就是 Menger 定理 的一个特殊情况. 而 Menger 定理又是 最大流最小割定理 的一个特殊情况.

总之, 可以很简单的用最大流最小割定理证出来. 比较显然.

引理 2: 一个点-双连通分量中要么每条边都在至少一个奇环上, 要么没有奇环.

这个也很容易用上面的那个性质证明吧…


最后, 怎么判断一个点双中是否存在奇环呢?

只需考虑是否存在一条非树边连接了两个深度奇偶性相同的点即可, 充分性显然, 必要性反证法即可.

Story

这是一道有故事的题…

首先在某次联赛模拟中见到这道题, 刚了好久也没刚出来. 模拟结束之后有人有 80 分, 结果是一个萎爆了的算法…

于是下午看了下搬题人的题解, 看到"强连通分量"就不想看下去了. 无向图的强连通分量?? 黑人问号.

后来看了看标程, 发现求了个边-双连通分量, 仔细想了想, 于是证明了引理 1. 觉得应该没问题了, 又和其他人讨论了一下, 发现一个严重的问题.

边双你大爷啊! 应该是点双啊!

于是就愉快地把标程 hack 掉了, 期间还一度怀疑这题是萎的, 后来发现这是 CF 原题之后才开始静下心来思考… 发现是点双之后, 觉得自己会证了, 就开始打了.

晚上写题解, 证引理 2 的时候, 发现"两个点在同一个点数大于 \(2\) 的点-双连通分量中, 当且仅当存在至少一个简单环, 这两个点都在环上"这个看似很显然的性质我并不会证, 在网上查也大多是一句话带过. 最后比较晚的时候发现了 Menger 定理这个东西, 看到用最大流最小割定理证以后恍然大悟.

太爷啦!!!

Comments

Comments powered by Disqus