无向图三元图和四元图计数

对于原图 $G=(V,E)$ ，首先我们给每条边定向。将度数小的节点向度数大的节点连边，如果度数一样，则按节点编号（这点很重要！！！否则无法产生偏序关系！！！）。产生新图 $G'=(V,E')$

然后可以有一个结论，就是对于任意顶点 $u\in V$，有 $\deg_u^+\leq \sqrt{m}$。

可以用反证法来证明

这么做有一个好处，就是我们可以遍历每条边 $u\rightarrow v$，然后在任意一个顶点 $u$ 或 $v$ 继续遍历以它为出发点的所有边，这么做的复杂度是 $m\sqrt{m}$ 的。

换句话来说，我们可以在 $O(m\sqrt{m})$ 里枚举所有的 $u\rightarrow v$，$v\rightarrow w$，或者是$u\rightarrow v$，$u\rightarrow w$，因为它们的总量是 $m^{1.5}$ 级别的。

当然要注意，只能以 $u$ 和 $v$ 为出发的节点，不能是到达的节点，因为我们只能保证它的出度，无法保证入度。

现在考虑三元环计数的问题，对于原图 $G$ 上的三元环 $(u,v,w)$，我们可以对应到新图 $G'$ 上的三元环 $(u,v,w)$，其中满足 $u\rightarrow v$，$v\rightarrow w$，$u\rightarrow w$。并且这是一个双射（即一一映射）。

考虑枚举 $u$，首先枚举它的所有出边，并对所有 $w$ 打上一个标记，说明它是能由 $u$ 直接到达。然后枚举 $u\rightarrow v$, $v\rightarrow w$，并用原来打在 $w$ 上的标记看它是否能由 $u$ 直接到达。

这样我们便在 $m^{1.5}$ 里解决了三元环计数问题

接着我们来看四元环问题。

一样的道理，对于原图 $G$ 上的四元环 $(A,B,C,D)$，映射到新图 $G'$ 上可能有如下几种情况。

至于这三个类型怎么想出来，可以画一个四元环，然后钦定第一个节点度数最小，这样两条边的方向就定了（这里也可以看出确定偏序关系的重要性），剩下两条边共 $4$ 种定向方式，并且有两种是一样的，所以就把这三个给定出来了。

对于第一种情况，固定 $B$，在 $m^{1.5}$ 时间里枚举 $A\rightarrow B$，$A\rightarrow D$，在 $m^{1.5}$ 时间里枚举 $B\rightarrow C$，$C\rightarrow D$。并把结果存在 $D$ 里。

对于第二种情况，固定 $A$，直接枚举 $A\rightarrow B$，$B\rightarrow C$ 和 $A\rightarrow D$，$D\rightarrow C$，把答案存在 $C$ 上，注意求的是 $\dbinom{f_C}{2}$，复杂度 $m^{1.5}$

对于第三种情况，固定 $B$，枚举 $A\rightarrow B$， $A\rightarrow D$ 和 $C\rightarrow B$，$C\rightarrow D$。可以在 $m^{1.5}$ 做完。

至于五元环以上的计数问题，目前没有 $m^2$ 以内算法。