跳到主要内容

环计数

参考资料​

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

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

无向图 GG 的三元环指的是一个 GG 的一个子图 G0G_0，满足 G0G_0 有且仅有三个点 u,v,wu, v, w，有且仅有三条边 ⟨u,v⟩,⟨v,w⟩,⟨w,u⟩\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle。两个三元环 G1,G2G_1, G_2 不同当且仅当存在一个点 uu，满足 u∈G1u \in G_1 且 u∉G2u \notin G_2。

题解

参考资料​

题意简述​

给定一张简单无向图，求其三元环个数。

解题思路​

顶点 xx 的度数记为 deg⁡(x)\deg(x)，入度记为 in⁡(x)\operatorname{in}(x)，出度记为 out⁡(x)\operatorname{out}(x)。

将每条无向边按两点的 (deg⁡(x),x)(\deg(x),x) 从小到大定向，得到一张有向无环图（DAG），因为这是 严格全序。

在新图中枚举 uu，并按 u→wu\to w 和 u→v→wu\to v\to w 计数，每个三元环只会被顺序最小的顶点统计 11 次。

考虑每个顶点 vv，根据定向规则：

out⁡(v)≤deg⁡(v)≤deg⁡(w),∀w∈Gv\operatorname{out}(v)\le\deg(v)\le\deg(w),\forall w\in G_v out⁡(v)2≤∑w∈Gvdeg⁡(w)≤2m\operatorname{out}(v)^2\le\sum_{w\in G_v}\deg(w)\le 2m out⁡(v)≤O(m)\operatorname{out}(v)\le O(\sqrt{m})

因此时间复杂度为：

T=O(∑u∑v∈Guout⁡(v))=O(∑vin⁡(v)out⁡(v))≤O(∑vin⁡(v)m)=O(m∑vin⁡(v))=O(mm)\begin{aligned} T &= O\left(\sum_u\sum_{v\in G_u}\operatorname{out}(v)\right) \\ &= O\left(\sum_v\operatorname{in}(v)\operatorname{out}(v)\right) \\ &\le O\left(\sum_v\operatorname{in}(v)\sqrt{m}\right) \\ &= O\left(\sqrt{m}\sum_v\operatorname{in}(v)\right)=O(m\sqrt{m}) \end{aligned}

参考代码​

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

const int N=200005;
int deg[N],tag[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>> a(m);
	for(auto &[u,v]:a)
	{
		cin>>u>>v;
		deg[u]++;
		deg[v]++;
	}
	for(auto [u,v]:a)
	{
		if(make_pair(deg[u],u)>make_pair(deg[v],v))swap(u,v);
		G[u].push_back(v);
	}
	int ans=0;
	for(int u=1;u<=n;u++)
	{
		for(int w:G[u])tag[w]=u;
		for(int v:G[u])for(int w:G[v])if(tag[w]==u)ans++;
	}
	cout<<ans<<'\n';
	return 0;
}