给定一张无向图，包含 \(n\) 个点，\(m\) 条边，求其中的三/四元环个数。
三元环计数
- 将边定向，度数大的连向度数小的。
- 枚举点 \(u\)，将 \(u\) 的出点打上标记。
- 枚举 \((u,v)\)，再枚举 \((v,w)\)，如果 \(w\) 上有 \(u\) 的标记，令 \(ans\leftarrow ans+1\)。
总体时间复杂度为 \(O(m\sqrt m)\)。
证明：分类讨论。
- 对于出度 \(\le \sqrt m\) 的所有点 \(v\)，一共最多被枚举 \(m\) 次，时间复杂度为 \(O(m\sqrt m)\)。
- 对于出度 \(\gt \sqrt m\) 的所有点 \(v\)，一共最多被枚举 \(\sqrt m\) 次，时间复杂度为 \(O(m\sqrt m)\)。
因此时间复杂度为 \(O(m\sqrt m)\)。
四元环计数
先鸽着。有人看到戳我一下。
三/四元环计数
原文：https://www.cnblogs.com/VCLS01/p/14846696.html
