无向图的三元环 - 四元环计数

问题描述：

给定一个$n$个点$m$条边的无向图，统计其中三元环/四元环的个数

考虑枚举一条边$(u,v)$，为了避免重复我们可能令$u<v$

然后暴力枚举求出$u,v$两个点出边的交点个数

具体的，先对于$u$的出点打标记，然后查询$v$的出点中被标记的个数

tips:当然每个三元环会被算三次

这样复杂度显然是$O(nm)$的，当$v$点度数大时就可以卡掉

强制$deg_u>deg_v\or deg_u=deg_v,u<v$

考虑先固定$u$，预处理出标记情况，然后枚举每个合法的$(u,v)$

再去枚举$v$的出边

考虑证明这个复杂度上限为$O(m\sqrt m)$级别

假设对于$(u,v)$

1.如果$deg_v\leq \sqrt m$，显然它们被枚举的次数总和$\leq m$，枚举复杂度为$O(m\sqrt m)$

2.对于$deg_v>\sqrt m$，则显然有$deg_u\ge deg_v>\sqrt m$

会枚举到$v$的$u$显然不超过$\sqrt m$个，因此这样的$v$遍历次数为$O(m\sqrt m)$

故复杂度为$O(m\sqrt m)$

$\$

类似三元环的方法，同样按照$(deg_u,u)$二元组递减的顺序设定排名

强制$u$为四元环中排名最小的点，枚举合法的边$(u,v)$，那么我们计算的实际上是每个$v$的出边的交的个数

依次枚举每个$v$的过程中，对于出边$(v,w)$维护$w$出现次数，即可求出交点个数

容易发现这样的计算不会出现重复

而复杂显然是与上面相同的，还去掉对于$u$的出点打标记的过程

orangejuice's blog