求无向图的三元环个数_怎么求无向图的三元组个数

问题描述：

给定$n$个点，$m$条边的无向图，求三元环个数。
$n\le 100000，m\le min(200000,n\ast (n-1)/2)$

问题分析：

搜集到的比较好的解法主要有两种：

法一： 把边定向后枚举一条边

先按照原图的边求出每个点的度数，然后把原图的无向边改为有向边：度数小的向度数大的连边，度数相同由编号小的向编号大的连边。（其实按照度数排序就可以了，我们记$u$排序之后的顺序为$rn{k}_u$）

如果你是把边改成了有向边，那么可以保证现在每个点的出度$\le \sqrt{m}$，然后枚举一条边(u,v)，然后遍历其中一个端点的邻接点打上标记，再遍历另一个端点的邻接点，遇上标记就ans++。复杂度$O(m\sqrt{m})$。

如果你是按照度数排序，那么枚举一条边(u,v)($rn{k}_u<rn{k}_v$)，遍历u的邻接点w ($rn{k}_w>rn{k}_u$)，如果v与w联通，ans++。当u的度数$\ge \sqrt{m}$时，w的个数$\le \sqrt{m}$。故复杂度也是$O(m\sqrt{m})$的。

如果懒得把边定向，也可以直接枚举原图边，用hash表记录邻接情况（譬如边(a,b)表示成an+b和bn+a），再枚举边的度数小的端点，判断是否与另一个端点联通，每个环算了三遍，答案最后需要除以3。均摊复杂度似乎仍然是$O(m\sqrt{m})$，但也许会慢一些。

法二：把点按度数分类

从1~n枚举每个点x，把x的邻接点y按度数分类，并打上标记：

• y的度数$\le \sqrt{m}$，直接枚举y的邻接点z，如果z被标记过，ans++。
  由于总共只会枚举m条xy边，所以这部分的总复杂度是$O(m\sqrt{m})$的。
• y的度数$>\sqrt{m}$，继续枚举x的邻接点z，如果y和z相连，ans++。
  由于这样的y的个数$\le \sqrt{m}$个，所以枚举y的复杂度为$O(m)$，枚举z的复杂度为均摊$O(\sqrt{m})$，总复杂度似乎也是$O(m\sqrt{m})$。（至于枚举z的复杂度的严格证明。。感性理解）

这个方法答案也要除以3。

Code：
咕掉了。。。