也许更好的阅读体验

问题描述

给一张 $n$n个点， $m$m条边的简单无向图，求解有多少个三元环
三元环：一个三元组 $(i,j,k)$(i,j,k)表示三个点，要求存在边 $(i,j),(i,k),(j,k)$(i,j),(i,k),(j,k)

解决方法

定义点的大小

我们先把每个点 $i$i定义一个双关键字 $(de{g}_i,i{d}_i)$(degi​,idi​)，其中 $de{g}_i,i{d}_i$degi​,idi​分别表示 $i$i点的度数与编号，这样每个点就有了严格的大小关系

转为有向图

然后我们将这张无向图转变为有向图：把所有的边 $(i,j)$(i,j)改为由关键字大的点向关键字小的点连边，这样我们就可以得到一张有向无环图

找环

找环分为三步

• 枚举一个点 $i$i，将所有出边所连接的点标记为 $i$i
• 枚举一个由 $i$i连出的点 $j$j
• 枚举所有由 $j$j连出的点 $k$k，若 $k$k有标记了且该标记为 $i$i，就表明找到了一个三元环

这样做就保证了每个环只会被 $i$i所找到
时间复杂度，最高为 $O\left(m\sqrt{m}\right)$O(mm ​)

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧