三元环 四元环

枚举三元环

枚举无向图三元环,将无向图转变成有向图,对于一条无向边,定义它的方向为度数大的点连向度数小的点。

我们可以先枚举一个点(i),再枚举i连出的点(j),再枚举(j)连出的点(k),如果((i,k))有边,(ans++)

复杂度:O($m sqrt{m} $)

复杂度证明:考虑枚举(i)(j)等同于枚举每条边((i,j)),如果(j)的度数小于(sqrt{m}) ,那么对于每一条边((i,j)) 枚举的(k)的次数小于$ sqrt{m}$ 。如果(j)的度数大于(sqrt{m}) ,那么这样的(j) 的不会超过(sqrt{m}) 个,又(i) 点度数比(j)大,这样的(i)点也不会超过(sqrt{m})个,计算次数为

(cnt=sum_{j,deg[j]>sqrt{m}}indeg(j)*outdeg(j)<=sqrt{m}*sum_{j,deg[j]>sqrt{m}}outdeg(j)<=sqrt{m}*m)

枚举四元环

同三元环,将无向图转变成有向图,对于一条无向边,定义它的方向为度数大的点连向度数小的点。

我们可以先枚举一个点(i)
再枚举i连出的点(j)(无向图中),再枚举(j)连出的点(k)(有向图中),(ans+=num(k),num(k)++)
对每个i做的时候都重新清空num数组
这样对四元环在有向图的每个一种情况都恰好计算一次

复杂度:(O(m*sqrt{m}))

复杂度证明:同上

原文地址:https://www.cnblogs.com/zhongzero/p/11788484.html