并非无向图三元环计数

· · 算法·理论

你说得对，但这里并不讲 无向图三元环计数。

所以 K4（无向图四元完全图计数）！

How to do it？

由于这个东西看样子难于三元环计数（感谢 tzl 大神提醒并不是严格强于。），所以考虑在三元计数上优化。

注意到三元环计数有个很重要的性质：按照 deg（度数）自小往大连边，每个点的出边是 O(\sqrt m) 级别的，这里不证明，见 P1989 题解。

那么我们考虑在这个基础上扩展下去。

还是枚举子图上第一个点 i。

然后呢？

注意到子图上剩余三个点都是与这个点有连边的，且这剩余三个点也能构成一个三元环。

所以我们希望保留这个点邻域的点，然后再在邻域上三元环计数就行了啊。

然后你会发现即使保留邻域所有点和这些点的连边，时间还是爆炸。

那么我们直接只保留邻域点的连边不就行了。

于是我们开个 bitset 来存边即可。

对于加边，我们还是像三元环的枚举做法一样，枚举与 i 有边的 j,k 然后看 i,j,k 是否是个三元环，是的话就在 j\to k 之间连一条有向边。

那么之后就再用一次用 bitset 来一遍三元环计数就行了啊。

具体的，还是枚举与 i 有边的 j,k，然后若 j,k 有边，看一下 j,k 的邻域的共同点，可以用 bitset 的 & 操作来完成。

时间复杂度 O(\frac{m^2}w)，可以通过。

:::info[code]

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

const int N=1e5+5,sqrtm=650;
int n,m;
vector<int> e[N];
int dag[N];
int u[N],v[N];
int id[N],res,cnt;
bitset<sqrtm> b[sqrtm];

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        dag[u[i]]++,dag[v[i]]++;
    }
    for(int i=1;i<=m;i++){
        if(dag[u[i]]>dag[v[i]]) swap(u[i],v[i]);
        else if(dag[u[i]]==dag[v[i]]&&u[i]>v[i]) swap(u[i],v[i]);
        e[u[i]].push_back(v[i]);
    }
    for(int i=1;i<=n;i++){
        cnt=0;
        for(int j:e[i]) id[j]=++cnt,b[cnt].reset();
        for(int j:e[i]) for(int k:e[j]) if(id[k]) b[id[j]][id[k]]=1;
        for(int j:e[i]) for(int k:e[j]) if(id[k]) res+=(b[id[j]]&b[id[k]]).count();
        for(int j:e[i]) id[j]=0;
    }
    cout<<res;
    return 0;
}

:::

upd：修了一些语言上的问题。