四元环计数

作者：小小林熬夜学编程 | 2024-02-06 21:37:44

踩

四元环计数

想看就看吧
$f o r (u)$
$for(v : out _u)$
$for(w : adj_v)$
$a n s + = c n t [w] + +$

我们把无向图按度数从小往大连边，那么每个点的度数 $out_u<=O(\sqrt m)$
所以上面的过程是 $O(m\sqrt m)$ 的，至于他不重不漏，好像是有序的所以不重不漏。
如果要统计经过每个点的四元环个数。
在 $f o r (u)$ 大括号内后面再加上：
$for(v : out _u)$
$for(w : adj_v)$
$r e t [v] + = - - c n t [w]$

代码：

#include<bits/stdc++.h>
const int kN=1e5+5,MOD=1e9+7;
int n,m,a[kN],deg[kN];
long long s[kN],t[kN];
std::vector<int>e[kN];
#define G for(int y:e[x])if(great(x,y))for(int z:e[y])if(great(x,z))
inline bool great(int x,int y){return deg[x]!=deg[y]?deg[x]>deg[y]:x>y;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
        ++deg[u],++deg[v];
    }
    for(int x=1;x<=n;++x){
        G s[x]+=t[z],s[y]+=t[z],s[z]+=t[z]++;
        G s[y]+=--t[z];
    }//s[i] : the number of cir4 containing point i
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/64655