三四元环计数

问题

给出 $n,m$ 这样一张图，求图上所有的三、四元环。

定向引理

将每条边定向，使得 $u\to v$ 当且仅当 $\deg u\le \deg v$。

有性质：任意点出度不超过 $\sqrt m$。

证明：

• Case 1

  $\deg u \le \sqrt m$ 时，显然成立

• Case 2

  $\deg u > \sqrt m$ 时，若 $u\to v$，则 $\deg v>\sqrt m$。而这样的 $v$ 最多 $\sqrt m$ 种。

三元环计数

考虑一个定向的三元环：

$1\to 2\quad 2\to 3\quad 1\to 3$

这样的情况是唯一的。

我们暴力枚举 $1\to 2$，再枚举 $2\to 3$，再检查是否存在 $1\to 3$。

实际实现的时候通常采用打 tag 的方式解决第三步。

四元环计数

一个四元环的情况会有很多种。

我们先考虑其中度数最大的点，不妨记为 $1$。

那么 $2\to 1\quad 3\to 1$ 分别是两条与 $1$ 相邻的边。

发现 $4$ 需要满足的是它在原图上与 $2,3$ 连边并且 $\deg 4\le \deg 1$。

于是我们直接枚举 $4\longleftrightarrow 2$，然后枚举 $2\to 1$ ，把满足这样的全都加到 $1$ 这个位置上就行了。