三元环

无向图三元环

给定一张无重边、无自环的无向图

点数为 \(n\) ，边数为 \(m\) ，其中 \(n, m\) 同阶

求有多少个无序三元组 \((i, j, k)\) 满足：

• 有一条连接 \(i, j\) 的边
• 有一条连接 \(j, k\) 的边
• 有一条连接 \(i, j\) 的边

首先考虑暴力，枚举所有三元组判断是否满足条件，时间复杂度 \(O(n^3)\)

考虑更优秀的做法，我们对任何一条边，将其定向为从度数大的点连向度数小的点，若度数相同则从编号小的点连向编号大的点，此时这张图就是一张有向无环图

之后枚举每个点 \(u\) ，将所有 \(u\) 有出边的点都打上 \(u\) 的标记，再枚举所有打上标记的点 \(v\) 的所有有出边的点 \(w\) ，若 \(w\) 有被 \(u\) 标记过，那么 \((u, v, w)\) 就是一个三元环

证明正确性：

• 定向后的图是有向无环图

  每条边的连边判定点的大小关系具有传递性，即 \(i \to j \to k\) 时 \((i, k)\) 的边只能是 \(i \to k\) ，故定向后的图是有向无环图

• 每个三元环只会被统计一次

  

  显然，每个三元环只会在 \(u\) 处被统计一次

时间复杂度为 \(O(m \sqrt{m})\)

对于打标记这个操作，我们会遍历所有点与所有边，时间复杂度为 \(O(n + m)\)

对于访问 \(u, v, w\) 的操作，考虑每条边 \(u \to v\) 对实际按复杂度的贡献为 \(outdeg_v\) ，其中 \(outdeg_v\) 表示 \(v\) 的出度，这样就转化为求 \(\sum outdeg_i\)

不妨分类讨论

• \(outdeg_v \leq \sqrt{m}\) ，由于 \(u\) 连接 \(v\) ，因此 \(deg_u > deg_v\) ，这样的 \(u\) 的个数是 \(O(n)\) 的，因此时间复杂度为 \(O(n \sqrt{m})\)
• \(outdeg_v > \sqrt{m}\) ，那么由于 \(u\) 连接 \(v\) ，因此 \(deg_u > deg_v > outdeg_v > \sqrt{m}\) ，这样的 \(u\) 的个数是 \(O(\sqrt{m})\) 的，因此时间复杂度为 \(O(m \sqrt{m})\)

故总时间复杂度为 \(O(n + m + n \sqrt{m} + m \sqrt{m}) = O(m \sqrt{m})\)

应用

P1989 无向图三元环计数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, M = 2e5 + 7;

struct Edge {
	int u, v;
} E[M];

vector<int> e[N];

int deg[N], tag[N];

int n, m, ans;

signed main() {
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &E[i].u, &E[i].v);
		++deg[E[i].u], ++deg[E[i].v];
	}
	
	for (int i = 1, u, v; i <= m; ++i) {
		u = E[i].u, v = E[i].v;
		
		if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v))
			swap(u, v);
		
		e[u].push_back(v);
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j : e[i])
			tag[j] = i;
		
		for (int j : e[i])
			for (int k : e[j])
				if (tag[k] == i)
					++ans;
	}
	
	printf("%d", ans);
	return 0;
}

P6815 [PA2009]Cakes

竞赛图三元环

定义

每两个点都有连边的有向图称为竞赛图

性质

对于一个竞赛图，其要么是一个拓扑图，要么存在一个三元环（即若竞赛图中存在环，则一定是三元环）

证明

考虑反证法，若存在环且不是三元环，那么会有在大环上的三元组 \((i, j, k)\) 且存在边 \(i \to j, j \to k\) ，若 \(i, k\) 的连边方向为 \(k \to i\) ，则其就是三元环；若为 \(i \to k\) 那么会得到一个把 \(j\) 排除在外的小一点的环，递归证明最后也是一个三元环。故竞赛图中存在环，则一定是三元环

线性求法

直接选出三个点，考虑容斥掉不是三元环的情况，当且仅当这个三元组有一点出度为 \(2\) ，这样的三元组不可能构成环。答案即为