无向图三元环 & 四元环计数 小结

给定一个 nn 个点 mm 条边的简单无向图,求其三元环个数。

1n1051 \le n \le 10^51m2×1051 \le m \le 2 \times {10}^5

给定一个 nn 个点 mm 条边的简单无向图,点 ii 有点权 aia_i,求其所有本质不同的四元环中所有点的点权和,模 109+710^9+7

1n1051\le n\le 10^51m2×1051\le m\le 2\times 10^51ai1091\le a_i\le 10^9

三元环

三元环等价于 (x,y)(x,y)(y,z)(y,z)(x,z)(x,z)

考虑给原图定向,让度数大的连向度数小的,度数一样按编号。

这样定向后的图一定是 DAG。

有一个很暴力的想法是直接枚举 xx,然后:

  • 开一个桶 bb
  • 枚举 xx 出边指向的点 yy,枚举 yy 出边指向的点 zzbzbz+1b_z\to b_z+1
  • 枚举 xx 出边指向的点 yyansans+byans\to ans+b_y

这样做的时间复杂度是 O(mm)O(m\sqrt m) 的。

证明

dud_u 为点 uu 在原图中的度数。

一条边 xyx\to y 对时间复杂度的贡献显然为 outyout_yyy 的出度。

  • dymd_y\le \sqrt m:由于新的图是原图定向得来的,所以 outydymout_y\le d_y\le \sqrt m
  • dy>md_y>\sqrt m:这样的点只有 m\sqrt m 个;

综上,时间复杂度为 mmm\sqrt m

Q.E.D.

闲话

事实上,定向时由度数小的连向度数大的点在三元环计数中也可行。

证明

dud_u 为点 uu 在原图中的度数。

一条边 xyx\to y 对时间复杂度的贡献显然为 outyout_yyy 的出度。

  • dymd_y\le \sqrt m:由于新的图是原图定向得来的,所以 outydymout_y\le d_y\le \sqrt m
  • dy>md_y>\sqrt myy 在新图上的出边连向的点 zz 一定满足 dz>md_z>\sqrt m,这样的点最多只有 m\sqrt m 个,所以 outymout_y\le \sqrt m

综上,时间复杂度为 mmm\sqrt m

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;
}

四元环

四元环等价于 (x,y),(y,z)(x,y),(y,z)(x,w),(w,z)(x,w),(w,z)

按照三元环的方式给图定向,即度数大的连向度数小的。记新图为 GG',原图为 GG

GG' 显然是 DAG,随意取它的一个拓扑序,设 uu 的排名为 rkurk_u

直接枚举 xx,然后:

  • 开两个桶 cntcntsumsum
  • GG’ 中枚举 xx 出边指向的点 yy,在 GG 中枚举 yy 出边指向的点 zz
    • ansans+sumz+cntz×ayans\to ans+sum_z+cnt_z\times a_y
    • rkz<rkxrk_z<rk_xcntzcntz+1cnt_z\to cnt_z+1sumzsumz+ax+ay+azsum_z\to sum_z+a_x+a_y+a_z
  • 清空两个桶;

可以看成是每次删除 rkxrk_x 最大的点 xx 并统计答案,这样做的时间复杂度是 O(mm)O(m\sqrt m) 的。

证明和三元环的第一个证明是一样的。

代码如下:

#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;
}

闲话

三元环和四元环计数的本质都是找有 33 个点的简单链,那么 nn 个点 mm 条边的无向图中有 kk 个点的本质不同的简单链个数的级别是怎么样的呢?

k=1k=1O(n)O(n)

k=2k=2O(m)O(m)

k=3k=3O(mm)O(m\sqrt m)

能否得出一个结论:k2k\ge 2 时级别是 O((m)k)O((\sqrt m)^k) 的?