给定一个 个点 条边的简单无向图,求其三元环个数。
,。
给定一个 个点 条边的简单无向图,点 有点权 ,求其所有本质不同的四元环中所有点的点权和,模 。
,,。
三元环
三元环等价于 ,,。
考虑给原图定向,让度数大的连向度数小的,度数一样按编号。
这样定向后的图一定是 DAG。
有一个很暴力的想法是直接枚举 ,然后:
- 开一个桶 ;
- 枚举 出边指向的点 ,枚举 出边指向的点 ,;
- 枚举 出边指向的点 ,;
这样做的时间复杂度是 的。
证明
设 为点 在原图中的度数。
一条边 对时间复杂度的贡献显然为 即 的出度。
- :由于新的图是原图定向得来的,所以 ;
- :这样的点只有 个;
综上,时间复杂度为 。
Q.E.D.
闲话
事实上,定向时由度数小的连向度数大的点在三元环计数中也可行。
证明
设 为点 在原图中的度数。
一条边 对时间复杂度的贡献显然为 即 的出度。
- :由于新的图是原图定向得来的,所以 ;
- : 在新图上的出边连向的点 一定满足 ,这样的点最多只有 个,所以 ;
综上,时间复杂度为 。
Q.E.D.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int S=100005;
int n,m,a[S];
vector<int> g[S],g2[S];
int id[S],rk[S];
int cnt[S];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y),g[y].push_back(x);
}
for(int i=1;i<=n;i++) id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){return g[x].size()<g[y].size();});
for(int i=1;i<=n;i++) rk[id[i]]=i;
for(int u=1;u<=n;u++) for(int v:g[u]) if(rk[v]<rk[u]) g2[u].push_back(v);
long long ans=0;
for(int x=1;x<=n;x++)
{
for(int y:g2[x]) for(int z:g2[y]) cnt[z]++;
for(int y:g2[x]) ans+=cnt[y];
for(int y:g2[x]) for(int z:g2[y]) cnt[z]=0;
}
printf("%d\n",ans);
return 0;
}
四元环
四元环等价于 和 。
按照三元环的方式给图定向,即度数大的连向度数小的。记新图为 ,原图为 。
显然是 DAG,随意取它的一个拓扑序,设 的排名为 。
直接枚举 ,然后:
- 开两个桶 和 ;
- 在 中枚举 出边指向的点 ,在 中枚举 出边指向的点 :
- ;
- 若 则 ,;
- 清空两个桶;
可以看成是每次删除 最大的点 并统计答案,这样做的时间复杂度是 的。
证明和三元环的第一个证明是一样的。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int S=100005,p=1000000007;
int n,m,a[S];
vector<int> g[S],g2[S];
int id[S],rk[S];
int cnt[S],bu[S];
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 x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y),g[y].push_back(x);
}
for(int i=1;i<=n;i++) id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){return g[x].size()<g[y].size();});
for(int i=1;i<=n;i++) rk[id[i]]=i;
for(int u=1;u<=n;u++) for(int v:g[u]) if(rk[v]<rk[u]) g2[u].push_back(v);
int ans=0;
for(int x=1;x<=n;x++)
{
for(int y:g2[x])
{
for(int z:g[y])
{
if(rk[z]>=rk[x]) continue;
ans=(0ll+ans+bu[z]+1ll*cnt[z]*a[y]%p)%p;
cnt[z]++;
bu[z]=(0ll+bu[z]+a[x]+a[y]+a[z])%p;
}
}
for(int y:g2[x]) for(int z:g[y]) cnt[z]=bu[z]=0;
}
printf("%d\n",ans);
return 0;
}
闲话
三元环和四元环计数的本质都是找有 个点的简单链,那么 个点 条边的无向图中有 个点的本质不同的简单链个数的级别是怎么样的呢?
:;
:;
:;
能否得出一个结论: 时级别是 的?