三元环（四元环）计数

· · 个人记录

模板题：P1989 无向图三元环计数

算法流程：

设 d_x 为 x 的度数。对图中所有边定向，若 d_x<d_y 或 d_x=d_y 且 x<y，则从 x 向 y 连边，否则从 y 向 x 连边。

容易发现图变为一个 DAG，有向边 (a,b) (a,c) (b,c) 和原图中三元环 a,b,c 一一对应。

先枚举一个点 i，并对 i 的所有出边打上时间戳标记。然后枚举 i 的出边 (i,j)，再枚举 j 的出边 (j,k)，若 k 的标记是新打上的（即存在边 (i,k)），则答案加 1。

时间复杂度 O(m\sqrt m)。通过此算法也可以说明无向图的三元环个数上界是 m\sqrt m。

复杂度证明：

设 id_x 为 x 的入度，od_x 为 x 的出度。

考虑计算枚举过程中 j 的贡献，所求即为 \sum id_j\times od_j。

因为 j 的出边一定连向度数大于 j 的点，这样的点个数不超过 \dfrac{m}{d_j}，所以 od_j\leq \dfrac{m}{d_j}，又因为 id_j\leq d_j，所以 id_j\times od_j\leq m。

于是有：

\sum id_j\times od_j\leq \sum \min(m,d_j^2)\leq \sum \sqrt{m\times d_j^2}=\sqrt m\times\sum d_j=m\sqrt m

因此复杂度为 O(m\sqrt m)。如果改为度数大的点向度数小的点连边，复杂度也相同。

提交记录

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3,M=2e5+3;
basic_string<int>g[N];
int v[N],a[M],b[M],d[N];
int main(){
    int n,m,i,j,k,s=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)scanf("%d%d",a+i,b+i),++d[a[i]],++d[b[i]];//统计度数
    for(i=1;i<=m;++i)if(d[j=a[i]]<d[k=b[i]]||(d[j]==d[k]&&j<k))g[j]+=k;else g[k]+=j;//给边定向
    for(i=1;i<=n;++i){
        for(int j:g[i])v[j]=i;//打时间戳
        for(int j:g[i])for(int k:g[j])s+=v[k]==i;//统计答案
    }
    printf("%d",s);
    return 0;
}

习题：

CF985G Team Players（容斥）

P3547 [POI2013]CEN-Price List（双向链表）

P4619 [SDOI2018]旧试题（莫比乌斯反演）

四元环计数：

首先和三元环计数一样将边定向。

然后有一个想法：四元环可以用两个 x\to y\to z 拼起来，枚举 x，然后向三元环计数一样枚举 y,z，对每个 x 和 z 记一个 cnt_{x,z} 表示这样的 x\to y\to z 的数量，对答案的贡献即为无序对的个数，即 \dfrac{cnt_{x,z}\times(cnt_{x,z}-1)}{2}。

然而这样做是错误的！

为什么三元环可以这样对边定向？因为三元环是无序的，三个点 x,y,z 至多存在一个三元环。而四元环是有序的，x,y,z,w 和 x,z,y,w 是不同的四元环。用上面的方法枚举四元环得到的答案比真实答案少。

考虑先对所有点按度数 d 为第一关键字，编号为第二关键字，从小到大排序。记 rk_x 为排序后 x 的排名。错误的做法大概是这样：

for(int j:g[i])if(rk[j]>rk[i])for(int k:g[j])if(rk[k]>rk[j])s+=c[k]++;

正确的做法是：

for(int j:g[i])if(rk[i]>rk[j])for(int k:g[j])if(rk[i]>rk[k])s+=c[k]++;

为什么这样做是正确的？确定了 rk 最大的点 i，以及和 i 在环上相对的点 k，再任意取两个 rk 小于 i 的和 i,k 都相连的点 j,l，就确定了一个四元环 i,j,k,l。统计无序对 j,l 的个数即可。注意 i 必须是 rk 最大的点，而不是 rk 最小的点，否则不能保证复杂度。

这种做法的时间复杂度同样是 O(m\sqrt m)。证明：对于每个 j，i 的度数大于 d_j，这样的 i 至多有 \dfrac{m}{d_j} 个，而 k 的个数不超过 d_j，乘起来就不超过 m。接下来用和三元环一样的证明方法即可。

注意四元环的个数上界是 O(nm\sqrt m)，可能需要开 long long。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
basic_string<int>g[N];//此处 g 存的是原图
int rk[N],a[N],d[N],c[N];
int main(){
    int n,m,i,j;
    long long s=0;
    scanf("%d%d",&n,&m);
    while(m--)scanf("%d%d",&i,&j),g[i]+=j,g[j]+=i,++d[i],++d[j];
    for(i=1;i<=n;++i)a[i]=i;
    sort(a+1,a+n+1,[](int x,int y){return d[x]<d[y]||(d[x]==d[y]&&x<y);});
    for(i=1;i<=n;++i)rk[a[i]]=i;
    for(i=1;i<=n;++i){
        for(int j:g[i])if(rk[i]>rk[j])for(int k:g[j])if(rk[i]>rk[k])s+=c[k]++;
        for(int j:g[i])if(rk[i]>rk[j])for(int k:g[j])c[k]=0;//清空
    }
    printf("%lld",s);
    return 0;
}

参考资料：

三元环小记(+四元环) command_block

三元环、四元环计数 mrclr