三元环计数类问题总结

## 完全图三元环计数 答案就是$\dbinom{n}{3}$ ## 竞赛图三元环计数 用总方案数-不合法的方案数即可 总方案数就是$\dbinom{n}{3}$，对于每个不合法的三元环，一定有一个点指向三元环中其他两个点，所以每个点贡献应该是：$\dbinom{out_i}{2}$减掉就好了 ## 无向图三元环计数 首先有一个暴力做法，枚举每一条边，枚举所有出边，把所有能到达的点都打上标记，检查是否打过标记，最后答案除以3就行了，这复杂度是$O(M^2)$ 然后其实可以只对于每一条边，我们可以把他转成有向图，只需要把入度小的点连向入读大的点，若一样则编号小的连编号大的，这样我们可以保证我们暴力做法中，每个点指向的边数大于$\sqrt m$的点不会超过$\sqrt m$个，复杂度为$O(M\sqrt M)$ 这样为什么是对的呢？ 首先，转化后不可能存在有向三元环（$du[a]≥du[b]≥du[c]≤du[a]$），然后还是像暴力一样，暴力枚举，存在三元环当且仅当一个点出度为2，统计这个点就行了 ## 有向图三元环计数 先转成无向图，再按上述方式转成有向图，每找到一个三元环判断在原图中边的方向即可（注意需要提前记录原图中边的方向）