环计数

参考资料

• 环计数问题 - OI Wiki

简介

三元环计数（Triangle Counting）要求统计无向简单图中所有满足三点两两相邻的无序三元组 $(u,v,w)$ 的数量。

算法基于边定向：将每条无向边 $(u,v)$ 定向为从度数较小的端点指向度数较大的端点（度数相同则从编号较小指向较大）。定向后图为 DAG。枚举每个节点 $u$，标记 $u$ 指向的所有节点，再枚举 $u$ 的出边邻居 $v$ 的出边邻居 $w$，若 $w$ 被标记则 $(u,v,w)$ 构成三元环。时间复杂度 $O(m\sqrt{m})$。

实现

612 Bcpp

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int deg[N];
bool vis[N];
vector<int> G[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>> edges(m);
	for(auto &[u,v]:edges)
	{
		cin>>u>>v;
		deg[u]++;deg[v]++;
	}
	for(auto [u,v]:edges)
	{
		if(deg[u]<deg[v]||(deg[u]==deg[v]&&u<v))G[u].push_back(v);
		else G[v].push_back(u);
	}
	int ans=0;
	for(int u=1;u<=n;u++)
	{
		for(auto v:G[u])vis[v]=1;
		for(auto v:G[u])
		{
			for(auto w:G[v])
			{
				if(vis[w])ans++;
			}
		}
		for(auto v:G[u])vis[v]=0;
	}
	cout<<ans<<'\n';
	return 0;
}

例题

洛谷 P1989 【模板】无向图三元环计数

无向图 $G$ 的三元环指的是一个 $G$ 的一个子图 $G_0$，满足 $G_0$ 有且仅有三个点 $u, v, w$，有且仅有三条边 $\langle u, v\rangle,\langle v, w\rangle,\langle w, u\rangle$。两个三元环 $G_1, G_2$ 不同当且仅当存在一个点 $u$，满足 $u\in G_1$ 且 $u\notin G_2$。