考虑对无向图的边进行定向，度数小的点连向度数大的点，如果度数相同则编号小的点连向编号大的点。 然后再这张新图(有向图)中我们枚举所有点 u u u，对于每个点 u u u我们枚举它的出边对应的端点 v v v，先给这些点打上标记，然后再枚举 u u u的出边对应的端点 v v v，枚举 v v v的出边对应的端点 w w w,如果 w w w是标记点的话就找到一个三元环，每个三元环都一定只会被恰好枚举一次，因此找到一个三元环就 + + a n s ++ans ++ans即可，注意枚举下一个 u u u之前需要清空标记数组。
考虑正确性，经过重定向后新图一定是一张无环的有向图，那么三元环只可能是如下图所示的形式： 容易发现只有再枚举 A A A的时候能够将该三元环计入答案。
由于枚举 u , v u,v u,v复杂度为 O ( n + m ) O(n+m) O(n+m)，考虑对于每个 v v v而言，假设它的出边有 k k k条，那么 d e g [ v ] ≥ k deg[v]ge k deg[v]≥k，那么这 k k k条边对应的端点 w w w的度数也一定至少为 k k k，因此 k ∗ k ≤ 2 m ⇒ k = O ( m ) k*kle 2mRightarrow k=O(sqrt m) k∗k≤2m⇒k=O(m )，即总复杂度约为 O ( ( n + m ) m ) O((n+m)sqrt m) O((n+m)m )。
这里以LuoGu P1989 无向图三元环计数为例给出一份参考代码：
#include using namespace std;const int maxn = 1e5+5;const int maxm = 2e5+5;struct EDGE{int u,v;}e[maxm];int vis[maxn],deg[maxn];vectorg[maxn];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;iv)swap(u,v);g[u].push_back(v); }int ans=0;for(int u=1;u B − > C A->B->C A−>B−>C统计一半，再走 A − > D − > C A->D->C A−>D−>C统计另一半，注意走第一条边的时候走的是原图的边！如果以 A C AC AC为轴线存在多个四元环，那么按照这种一半一半统计贡献的方式仍然是可以全部计算出来的。另外注意到新图 h h h中存在 A − > B − > C A->B->C A−>B−>C这样的拓扑链，说明 A A A的优先级是小于 C C C的，因此也能确保循环的能够进入最里层。再看一种特殊情况，那就是存在两个点都是两条边的指向，如下图所示： 上图中 A 、 C A、C A、C两点都是被两条边所指向的点，好像这个四元环会被统计两次，但实际上不会，因为 A 、 C A、C A、C必定存在一个优先级的大小之分(计算度数相同还要比较编号)，因此仍然只会被统计一次。
综上来说每个四元环都恰好被一个点统计一次，因此算法是正确的，复杂度分析与三元环的相同，就不多说了。下面给出一份参考代码：
#include using namespace std;const int maxn = 2e5+5;int d[maxn],id[maxn],rk[maxn],cnt[maxn];vectorg[maxn],h[maxn];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i