无向图三元环计数

\(O(n \sqrt m)\) 算法

bitset做法

第一次接触三元环计数是在 HEZ 的机房，打模拟赛的时候遇到一个“求长度为4的路径数量”的题目。然后要用容斥排除三元环，要求复杂度比 \(O(nm)\) 低。结果一个机房的蒟蒻都只会用 bitset 优化。这里先讲一下：

把图用 bitset 写的邻接表存下来，然后 \(O(m)\) 枚举三元环中的一条边 \((u, v)\) ，那么只要求出 \(u\) 的出边与 \(v\) 的出边的交集。利用 bitset 求交集可以直接将复杂度降低 64 （大概）倍。所以时间复杂度 \(O(\frac{nm}{\omega})\)

根号做法

但是这可太逊了，因为我发现了这样一题：

三元环计数

数据范围加强到了 \(10^5\) ，不仅空间开不下，时间也不够。

这时候就要回归暴力了。使用邻接表存图， \(O(m)\) 枚举一条边之后，时间复杂度的瓶颈就是有可能有一个点有 \(O(m)\) 条出边。如果我们能保证每个点的出边不超过一个阈值，比如 \(O(\sqrt m)\) 或 \(O(\log m)\) ，复杂度就得以降低。

先不急，先明确一个事：要实现这一点，必然是把无向图变成一个有向图，即删除一些出边很多的节点的边，降低度数。如果想在有向图上跑计数，就要保证这是一个有向无环图，否则会出现重复的情况。

所以我们的目标是：构建一个有向无环图，使得每个点的出边数量少一点 。

怎么做呢？我们先把无向图中的度存下来。对于每一条无向边，将度数小的点向度数大的点连边，如果度数一样，将编号较小的点向编号较大的点连边。

这样就是一条有向无环图（很显然，从一点出发，度数和编号都越走越大，不可能走回自己），并且出边数量为 \(O(\sqrt m)\) 。

为什么？

分类讨论：

• 如果原来无向图中的度数大于等于 \(\sqrt m\) ，注意到它只能向度数比自己大的点连边，而度数大于 \(\sqrt m\) 的点最多只有 \(\sqrt m\) 个。所以最多有 \(\sqrt m\) 条出边。
• 如果原来无向图中的度数小于 \(\sqrt m\) ，注意到有向图中的边来自于无向图，所以有向图中的出边不大于无向图中的度数，即小于 \(\sqrt m\) 条。

所以，任何点的出边都小于等于 \(\sqrt m\) 条。总时间复杂度 \(O(m \sqrt m)\) 。

例题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

#define FILE_IO
namespace io {
	///...
};
using namespace io;

const int maxn = 1e5 + 5;

int n, m, ans;
int uu[maxn * 2], vv[maxn * 2], d[maxn];
bool book[maxn];
vector<int> graph[maxn];

int main() {
	// freopen(".in", "r", stdin);
	// freopen("P1989.out", "w", stdout);
	read(n); read(m);
	for (int i = 1; i <= m; i++) {
		read(uu[i]); read(vv[i]);
		d[uu[i]]++; d[vv[i]]++;
	}
	for (int i = 1; i <= m; i++) {
		if (d[uu[i]] > d[vv[i]]) swap(uu[i], vv[i]);
		if (d[uu[i]] == d[vv[i]] && uu[i] > vv[i]) swap(uu[i], vv[i]);
		graph[uu[i]].emplace_back(vv[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int u : graph[i]) book[u] = true;
		for (int u : graph[i])
			for (int v : graph[u])
				ans += book[v];
		for (int u : graph[i]) book[u] = false;
	}
	write(ans);
	return 0;
}