三、四元环计数

无向图三元环计数：

定义一个有向图 \(G'\)：把 \(G\) 中每条边改成从度数小的点指向度数大的点 的有向边。

性质：\(G'\) 中每个点的出度 \(\le 2\sqrt m\)。

证明：若 \(u\) 的出度 \(>2\sqrt m\)，则显然 \(u\) 在原图中的度数 \(>2\sqrt m\)。所以 \(u\) 指向的至少 \(2\sqrt m + 1\) 个点的度数，也都 \(>2\sqrt m\)。（因为是度数小指向度数大的）

这 \(2\sqrt m\) 个点，每个点的度数都大于 \(2\sqrt m\)，则总边数显然 \(>m\)。

这个性质有什么用呢？

推论：（在 \(G'\) 中）枚举点 \(x\) ，再枚举 \(x\) 的后继 \(y\)，再枚举 \(y\) 的后继 \(z\) 的复杂度是 \(O(m\sqrt m)\) 的。

证明：可能有一种不准确的估计：\(x\) 点是 \(O(n)\) 枚举的，枚举 \(x\) 的后继 \(O(\sqrt m)\)，再枚举一个又乘 \(O(\sqrt m)\)，总复杂度是 \(O(nm)\) 的。但实际上，枚举 \(x\) 和 \(x\) 的后继，相当于枚举了所有边的起点，总复杂度不是 \(O(n\sqrt m)\) 而是 \(O(m)\) 的。所以总复杂度是 \(O(m\sqrt m)\)。

由此可以设计出我们的算法：

枚举点 \(a\)，枚举 \(a\) 的后继 \(b\)，将所有 \(b\) 打上标记；然后枚举所有 \(b\) 的后继 \(c\)，若 \(c\) 有标记，\(ans+1\)