QOJ7177 题解

· · 题解

求无向图上所有简单环环长的 \gcd。

所有简单环的数量是指数级别的，不过考虑到相交的两个环上有一个新环，这个新环的环长受到两个环的环长和相交部分的长度的制约，我们实际上需要考虑的因素应该不多。

具体地说，如果两个环长分别为 a,b，相交部分长度为 c，那么形成的第三个环环长为 a+b-2c，又有 \gcd(a,b,a+b-2c)=\gcd(a,b,2c)。

这启示我们通过较少的“基本”的环，用它们的环长和相交部分来刻画所有环，然后用类似上式的形式化简 \gcd。

研究图上环结构的基本方法是考察 dfs 树。无向图上每个环到其包含的非树边集合的映射构成单射。因为一条树边在某个环上当且仅当割开这条边后落在两侧的非树边端点均有奇数个。

所以我们可以用如下方式构造某个非树边集“生成”的环（如果这个简单环存在的话）：我们称一个以某条非树边两端为端点的路径为该非树边跨过的路径；将该非树边集合内每条边跨过的路径包含的树边做对称差，再并上该非树边集合。

生成的环长长什么样呢？大致是，所有①非树边和它跨过的路径构成的环的环长之和，减去②所有树边长度乘上被多包含的次数。根据 \gcd 的性质，因为每个非树边在①部分的贡献都已经算在 \gcd 中，所以我们可以只考虑②部分。

②部分的贡献具体是什么形式呢？每条边在①部分内贡献的次数是该非树边集中跨过自己的边数，根据我们的构造方式，我们会减去小于等于这个边数的最大偶数。进一步观察，我们根据该非树边集中跨过边 e 的非树边构成的集合 S_e，将 S_e 相同的树边划在同一个等价类中，每个等价类内的边一定是它对应的 S 中所有非树边跨过的树上路径的交；并且同一等价类内所有边对②部分造成的贡献的次数全部相同。

考虑到若干条树上路径的交一定可以表示成其中某两条路径的交（三条边的情形可以简单地分类讨论证明，然后可以归纳），也就是说对于一个等价类（一条树上路径），一定存在两条非树边“生成”的环，②部分的贡献是这条路径长度的两倍，所以我们可以用 \gcd 的性质再进行化简。

这里做法已经呼之欲出了，我们首先考虑上所有只包含一条非树边的环的环长，然后再把按照上述方法得到每种等价类（一条树上路径）大小的两倍考虑上。所有数求 \gcd 即可。因为等价类个数不可能超过树边个数，所以我们只用考虑 O(n) 个数。

具体实现时，可以用异或哈希求每个点所属等价类。

Submission on QOJ