无向图三元环计数（根号算法）

题目描述

         给定一个 $n$ 个点， $m$ 条边的简单无向图，求其三元环个数。 $1\le n\le 10^5，1\le m\le 2\times 10^5$。 保证图没有 重边 和 自环。但是不保证图联通。

分析：

暴力：

         我们考虑暴力该怎么做。注意到边数没有达到 $n^2$ 级别，而是跟 $n$ 同阶，我们考虑枚举边。
         我们枚举一条边，设这条边连接了两个点 $u$，$v$。那么我们再枚举一个点 $k$， $O(1)$ 的去判断是否存在边 $(u,k)$ 和 $(v,k)$。时间复杂度 $O(mn)$。
         但是这样做好像会有点浪费，因为如果 $k$ 至少和其中任何一个点连接才有枚举的价值。我们可以考虑枚举 $u$ 或者 $v$ 的所有连边，不妨枚举 $u$ 的所有连边，如果某一条连边所连接的点是 $k$，那么我们再 $O(1)$ 的判断是否有$(k,v)$ 这条边。 时间复杂度是 $O(m^2)$。
         我们接着考虑，如果我们每次枚举点 $u$ 是 $u,v$ 两个点中度数较小的那个，会不会能够很大的提高效率呢？ 如果 $u$ 是 $u,v$ 中度数较小的那个，设 $u$ 的度数为 $de{g}_u$。
         如果 $de{g}_u\le \sqrt{m}$，那么很显然 $m\times \sqrt{m}$ 不会超时。
         如果 $de{g}_u\ge \sqrt{m}$ 那么就意味着 $de{g}_v\ge \sqrt{m}$。我们考虑到所有点的度数之和为 $2m$，所以度数超过 $\sqrt{m}$ 的点的数量小于 $\sqrt{m}$ 个。首先因为没有重边，所以 $n^2\ge m$。所以 $n\ge \sqrt{m}$。并且每个点的度数小于等于 $n$。 我们想让所有点的度数都平均的尽可能大，考虑极端数据就是 $\sqrt{m}$ 个点，每一个点的度数都是 $\sqrt{m}+1$ 的完全图，我们考虑在这种情况下复杂度是 $O(m\sqrt{m})$ 的也不会超时。至于那种想让某几个点度数很大，其他点度数很小的菊花图，我们发现也只会在枚举个别边的时候复杂度会比较高，其他情况还是很小的。所以也超时不了。
         这样做好像可行了，应该能拿到不少的分了。

正解：

         我们把无向图变成 有向图，给每个边加一个方向。
         加方向的规则是，对于一条边 $(u,v)$ 而言，我们让其由度数小的点指向度数大的点。如果度数一样，就让编号小的点指向编号大的点。
         具体来讲， $u\to v$ 的条件是 $de{g}_u<de{g}_v$ 或者 $de{g}_u=de{g}_v$ 并且 $u<v$。
         我们发现，在这样的条件下，形成的有向图 一定无环，可以把连边规则看作是优先级，那么有向边就是某一组优先关系，所以一定不会存在环。 进一步，我们发现，原图中的所有环一定等价于所有的形如 $u\to v$， $u\to k$， $v\to k$ 的三元关系。我们只要找出来所有这样的三元关系就好了。
         方法是我们枚举一个点 $u$ 的所有出边，并且把所有出点 $v$ 打上时间戳为 $u$ 的标记。然后枚举所有 $v$ 的出边，如果有一个出点 $k$ 的时间戳是 $u$，那么让答案加1。这样做等价于 以每一个点作为环中优先级最低的点，找出所有这样的环的数量。所以是不重不漏的。

         我们来分析复杂度。
         首先就是任意一个点的出度不会超过 $\sqrt{m}$。因为如果一个点在原图中的度数小于 $\sqrt{m}$，那么在有向图上它都出度不会超过原图上的度数。所以小于 $\sqrt{m}$。
         如果一个点在原图中的度数大于 $\sqrt{m}$，但是连边的条件是度数小的点朝度数大的点连边，因为总边数为 $m$，所以度数大于 $\sqrt{m}$ 的点不会超过 $\sqrt{m}$ 个，因此这个点的出度也不会超过 $\sqrt{m}$。
         每一个点对复杂度的贡献是 $I{n}_i\times Ou{t}_i$， $I{n}_i$ 是 $i$ 号点的入度， $Ou{t}_i$ 是 $i$ 号点的出度。因为 $Ou{t}_i$ 是 $\sqrt{m}$ 量级，而 ${\sum }_{i=1}^{n}I{n}_i=m$。所以总复杂度是 $O(m\times \sqrt{m})$。

CODE：

#include
#define N 100100
#define M 200100
#define pb push_back
#define LL long long
using namespace std;
int n, m, u[M], v[M], deg[N], tim[N];
vector< int > E[N];
LL res;
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		scanf("%d%d", &u[i], &v[i]);
		deg[u[i]]++; deg[v[i]]++;
	}
	for(int i = 1; i <= m; i++){
		if(deg[u[i]] != deg[v[i]]){
			if(deg[v[i]] > deg[u[i]]) swap(u[i], v[i]);
			E[v[i]].pb(u[i]);//每一个里面放比它度数大的 
		}
		else{
			if(u[i] > v[i]) swap(u[i], v[i]);
			E[u[i]].pb(v[i]);
		}
	}
	for(int u = 1; u <= n; u++){
		for(auto v : E[u]){// 扫描出边， 复杂度O（m） 
			tim[v] = u;
		}
		for(auto v : E[u]){
			for(auto x : E[v]){//扫描出边的出边，每一条边会被扫到一次，一个边贡献√m的复杂度，所以总复杂度是O（m√m） 的 
				if(tim[x] == u) res++; 
			}
		}
	}
	printf("%lld\n", res);
	return 0;
}
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