四环（4-cycle）
在图上我们称他<a,b,c,d,a>使得四个点a,b,c,d依序相邻
我想问问大神存不存在比O(n^3)还快地找四环计数算法
算出一张simple graph上有几个4-cycle
拜托了>_< 我想过judge

无向图吗? 有 O(n^2) 的算法对每个点 x, 以及每对 x 的邻居 (y,z), A[y,z]++最后检查有没有某个 A[u,v] 的值大于 1如果图的边数不多的话有更外的算法http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf O(m^{4/3})*快抱歉，上面的算法应改进成一发现某格值已为 1 而要加为 2时就要停下不然最糟时会是 O(n^3)...

谢谢H大的回复 我花点时间啃一下论文

我之前有想过一个 O(n^2) 时间 O(n) 空间的方法不过只能侦测 4-cycle 存在而不是 counting从每个点作 BFS ，如果邻居的邻居有交集就是有4-cycle因为判断邻居的邻居的交集顶多使用 O(n) 空间所以总共的时间复杂度是O(n^2) 空间复杂度是O(n)

哎呀我没有意识到原 po 需要的是计数不是存在性…上面的推文是存在与否的算法另外请问 a,c 或 b,d 可相同吗？

但是论文可以解 counting 吧 虽然需要矩阵乘法

我指的是连结前面的那个

了解 所以只需要要快一点的矩阵乘法就可以压下去

用矩阵乘法就算的出来了