三元环&四元环计数-学习笔记

· · 个人记录

Thanks to iki9.

求出无向图的所有三元环：

首先要对所有的无向边进行定向，对于任何一条边，从度数大的点连向度数小的点，如果度数相同，从编号小的点连向编号大的点。

此时这张图是一个有向无环图。

之后枚举每一个点u，然后将u的所有相邻的点都标记上“被u访问了”，然后再枚举u的相邻的点v，然后再枚举v的相邻的点w，如果w存在“被u访问了”的标记，那么(u,v,w)就是一个三元环了。

而且每个三元环只会被计算一次。

时间复杂度O(M \sqrt{M})

例题：HDU 6184

    in(n),in(m);
    for(ri i=1,a,b; i<=m; ++i)
    {
        in(a),in(b);
        ++du[a],++du[b];
        ve.pb(mp(a,b));
    }
    for(ri i=0; i<size(ve); ++i)
    {
        int a=ve[i].fi,b=ve[i].se;
        if(du[a]>du[b]||(du[a]==du[b]&&a>b)) adde(a,b);
        else adde(b,a);
    }
    int ans=0;
    for(ri i=1; i<=n; ++i)
    {
        ++cur;
        for(ri j=head[i]; j; j=nx[j])
            vis[v[j]]=cur;
        for(ri j=head[i]; j; j=nx[j])
            for(ri k=head[v[j]]; k; k=nx[k])
                if(vis[v[k]]==cur) ++ans;
    }
    out(ans);

同样复杂度的四元环计数

（这道题有一个又难写，时间复杂度还高的超级分类讨论算法）

给每个点按照度数大小编不同的号。

枚举点u，枚举和点u相邻的点v，枚举v的相邻且度数比uv大的点z，ans+=cnt[z],++cnt[z];

复杂度：枚举uv的复杂度是O(n+m)的，然后点z的数量不超过O(\sqrt{m})个。

原因：设与x相邻的度数大于x的点y有s个，则x的度数至少为s，所以总边数s^2=2m

signed main()
{
    in(n,m);
    for(ri i=1,a,b; i<=m; ++i)
    {
        in(a,b);
        E[a].pb(b),E[b].pb(a);
    }
    for(ri i=1; i<=n; ++i) du[id[i]=i]=Size(E[i]);
    sort(id+1,id+1+n,cmp);
    for(ri i=1; i<=n; ++i) rk[id[i]]=i;
    for(ri u=1; u<=n; ++u)
        for(solid v:E[u])
            if(rk[v]>rk[u]) G[u].pb(v);
    LL ans=0;
    for(ri u=1; u<=n; ++u)
    {
        for(solid v:E[u])
            for(solid w:G[v])
                if(rk[w]>rk[u]) ans+=cnt[w]++;
        for(solid v:E[u])
            for(solid w:G[v])
                if(rk[w]>rk[u]) cnt[w]=0;
    }
    out(ans);
    return 0;
}

（第一层枚举G，第二层枚举E也是对的）

这种方法还可以求出每个点在多少三元环/四元环中。

更简单的方法？

令 v 是节点中度数最大的点。我们从 v 出发，遍历所有“距离 v 不超过 2“的点，复杂度是 O(\min(d^2_v,M)) ，其中 d_v 为 v 的度数。在遍历的过程中，你可以统计经过 v 的三元环、四元环的个数。

删除 v ，然后重复上面的过程，就能得到答案。

时间复杂度为 O(\sum_v min(d^2_v,M))=O(M\sqrt{M}) 。