三元环 学习笔记

今天考试考了一个找三元环的题。考场上回忆了一会三元环计数，发现忘了，再看数据范围发现很小，bitset随便氵过去了。不过还是很有必要学一下。 这种三元环计数算法的复杂度是$O(m \sqrt m)$，用bitset计数的复杂度是$O(\frac{nm}{32})$。

无向图三元环计数

暴力

枚举一条边，枚举其中一个点的出点，打上标记，再枚举另一个点出点。$O(m^3)$

暴力优化

把无向图变成有向图，规则如下：如果两个点度数不一样，从小的连向大的。如果两个点度数$deg$相同，从编号小的连向大的。 这样的图中没有环，是DAG。现在，枚举一个点，把这个点出边指向的点都打上标记。再枚举出点，枚举出点的出点，找出三元环。 DAG证明：如果有环，环上点$deg$不同显然不行。如果相同，不可能产生一圈，每个点指向的点都比自身编号大。 复杂度证明：复杂度的瓶颈显然在枚举出点的出点。对于一条边$x \to y$，对复杂度的贡献就是$deg_y$。对$deg$分块，分类讨论点数边数即可。 不会重复计数证明：没有环，所以三元环内一定有一个点向其它两个点连了边，三元环只会在这个点被计算一次。

有向图三元环计数

实际上，三元环的数量就是$O(m \sqrt m)$的，直接全找出来判断就行了。。

竞赛图三元环计数

竞赛图上如果有环，那么一定是三元环。用容斥直接求答案，随便选三个点，再去掉一个点出度为$2$的情况。 $$\binom{n}{3} - \sum_{i=1}^n \binom{out_i}{2}$$