四元环计数
想看就看吧
f
o
r
(
u
)
for(u)
for(u)
f
o
r
(
v
:
o
u
t
u
)
for(v : out _u)
for(v:outu)
f
o
r
(
w
:
a
d
j
v
)
for(w : adj_v)
for(w:adjv)
a
n
s
+
=
c
n
t
[
w
]
+
+
ans += cnt[w] ++
ans+=cnt[w]++
我们把无向图按度数从小往大连边，那么每个点的度数
o
u
t
u
<
=
O
(
m
)
out_u<=O(\sqrt m)
outu<=O(m)
所以上面的过程是
O
(
m
m
)
O(m\sqrt m)
O(mm)的，至于他不重不漏，好像是有序的所以不重不漏。
如果要统计经过每个点的四元环个数。
在
f
o
r
(
u
)
for(u)
for(u)大括号内后面再加上：
f
o
r
(
v
:
o
u
t
u
)
for(v : out _u)
for(v:outu)
f
o
r
(
w
:
a
d
j
v
)
for(w : adj_v)
for(w:adjv)
r
e
t
[
v
]
+
=
−
−
c
n
t
[
w
]
ret[v] += --cnt[w]
ret[v]+=−−cnt[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;
}