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

给定一个 $n$ 个点 $m$ 条边的简单无向图，求其三元环个数。

$1 \le n \le 10^5$，$1 \le m \le 2 \times {10}^5$。

给定一个 $n$ 个点 $m$ 条边的简单无向图，点 $i$ 有点权 $a_i$，求其所有本质不同的四元环中所有点的点权和，模 $10^9+7$。

$1\le n\le 10^5$，$1\le m\le 2\times 10^5$，$1\le a_i\le 10^9$。

三元环

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

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

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

有一个很暴力的想法是直接枚举 $x$，然后：

• 开一个桶 $b$；
• 枚举 $x$ 出边指向的点 $y$，枚举 $y$ 出边指向的点 $z$，$b_z\to b_z+1$；
• 枚举 $x$ 出边指向的点 $y$，$ans\to ans+b_y$；

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

#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,w),(w,z)$。

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

$G'$ 显然是 DAG，随意取它的一个拓扑序，设 $u$ 的排名为 $rk_u$。

直接枚举 $x$，然后：

• 开两个桶 $cnt$ 和 $sum$；
• 在 $G’$ 中枚举 $x$ 出边指向的点 $y$，在 $G$ 中枚举 $y$ 出边指向的点 $z$：
  • $ans\to ans+sum_z+cnt_z\times a_y$；
  • 若 $rk_z<rk_x$ 则 $cnt_z\to cnt_z+1$，$sum_z\to sum_z+a_x+a_y+a_z$；
• 清空两个桶；

可以看成是每次删除 $rk_x$ 最大的点 $x$ 并统计答案，这样做的时间复杂度是 $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;
}

闲话

三元环和四元环计数的本质都是找有 $3$ 个点的简单链，那么 $n$ 个点 $m$ 条边的无向图中有 $k$ 个点的本质不同的简单链个数的级别是怎么样的呢？

$k=1$：$O(n)$；

$k=2$：$O(m)$；

$k=3$：$O(m\sqrt m)$；

能否得出一个结论：$k\ge 2$ 时级别是 $O((\sqrt m)^k)$ 的？