无向图三元环计数

考虑给无向图定向，设 \(d_u\) 为点 \(u\) 的度数，对于无向边 \(\lang u,v\rang\)，若 \(d_u<d_v\) 或 \(d_u=d_v\) 且 \(u<v\)，我们在新图中连有向边 \(\lang u,v\rang\)，否则连有向边 \(\lang v,u\rang\)，容易发现新图必然是一张 DAG。

我们枚举三元环中的一个点 \(x\)，在新图中同时标记 \(x\) 的所有出边并枚举它的出边 \(\lang x,y\rang\)，枚举 \(y\) 的出边 \(\lang y,z\rang\)，如果存在边 \(\lang x,z\rang\)，那么 \((x,y,z)\) 就是原图中的一个三元环，正确性容易验证。

分析复杂度。设 \(d'_x\) 为点 \(x\) 在新图中的出度，\(E\) 为新图的边集，则时间复杂度即为 \(\displaystyle\mathcal{O}(\sum_{\lang x,y\rang\in E}d'_y)\)。以下将证明对任意一个点 \(y\)，\(d'_y\le\sqrt{m}\)：

• 若 \(d_y\le\sqrt{m}\)：显然有 \(d'_y\le d_y\le\sqrt{m}\)；
• 若 \(d_y>\sqrt{m}\)：则对于 \(y\) 的任意一条出边 \(\lang y,z\rang\)，有 \(d_z\ge d_y>\sqrt{m}\)，所以最多存在 \(\dfrac{m}{\sqrt{m}}=\sqrt{m}\) 个 \(z\)，因此 \(d'_y\le\sqrt{m}\)。

综上所述，\(d'_y\le\sqrt{m}\)，而一共只有 \(m\) 条边，所以总时间复杂度是 \(\mathcal{O}(m\sqrt{m})\) 的。