图上的三元环、四元环计数

虽然说这是图上计数的问题，但是方法还是非常简单的。

我们只考虑无向图的情况。有向图只需要在无向图的环求出之后验证一下就行了。

我们不妨假设图中的点标号为 /(1,2,/cdots,n/)。然后我们对这个无向图的边进行定向，从度数小的点连向度数大的点，如果度数相同就从标号小的点连向标号大的点。容易发现这是个偏序关系，连出来的一定是 DAG。
然后暴力枚举就完事了。

1. 三元环计数

我们的做法是枚举点 /(u/) 的所有出边并打上标记，然后对每个被打标记的点看是否能一步到达另外一个带标记的点。
看上去就是简单的暴力。但我们接下来证明复杂度是 /(O(m/sqrt{m})/)。
考虑三元环 /((a,b,c)/)，不妨设它在 DAG 上的形式为 /((a,b),(a,c),(b,c)/)（有向边）。容易发现每个三元环只会在 /(a/) 处被枚举一次。
另外容易发现前面枚出边的复杂度是线性的，关键在于枚举打标记的点的复杂度。
记点 /(u/) 的出度是 /(out_u/)，那么很明显统计次数就是 /(/sum/limits_{i=1}^m out_{v_i}/)。我们要尝试算出来这个式子。

考虑对每个点 /(u/) 在图上的总的度数 /(d_u/) 进行分类讨论。
比如说我们给定一个 /(B/)：

• /(d_u/leqslant B/Rightarrow out_u/leqslant d_u/leqslant B/)。
• /(d_u>B/Rightarrow/forall (u,v),d_v/geqslant d_u>B/)，又有 /(/sum/limits_{u}[d_u>B]</dfrac{m}{B}/)，故 /(out_u</dfrac{m}{B}/)。
  很明显取 /(B=/sqrt{m}/) 最优，此时有 /(/sum/limits_{i=1}^m out_{v_i}/leqslant m/sqrt{m}/)。

综上统计的时间复杂度是 /(O(m/sqrt{m})/)。

模板题

code:

int n,m,cnt,ans,h[maxn],deg[maxn],vis[maxn];
struct edge{int to,nxt;}e[maxm];
inline void addedge(int u,int v)
{
    e[++cnt]=(edge){v,h[u]};
    h[u]=cnt;
}
struct edg{int u,v;}ed[maxm];
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        ed[i]=(edg){u,v};
        deg[u]++;deg[v]++;
    }
    for(int i=1;i<=m;i++)
    {
        int nowu=ed[i].u,nowv=ed[i].v;
        if(deg[nowu]<deg[nowv]||(deg[nowu]==deg[nowv]&&nowu<nowv))
            addedge(nowu,nowv);
        else addedge(nowv,nowu);
    }
    for(int u=1;u<=n;u++)
    {
        for(int i=h[u];i;i=e[i].nxt)vis[e[i].to]=u;
        for(int i=h[u];i;i=e[i].nxt)
        {
            int p=e[i].to;
            for(int v=h[p];v;v=e[v].nxt)
                if(vis[e[v].to]==u)
                    ans++;
        }
    }
    printf("%d/n",ans);
    return 0;
}

2. 四元环