菜王的 blog

有个很妙的算法，可以在 $O(m \sqrt m)$ 的时间复杂度内统计无向图的三元环个数。

考虑给每个点赋权，然后令每条边定向，从权值小的连向权值大的，权值相同的，从编号小的连向编号大的，这样可以保证生成的新图是个 DAG。这样每个在原图中的三元环都是长这样的：

我们枚举 $u$，再枚举 $u$ 的出点 $v$，最后枚举 $v$ 的出点 $w$，看 $w$ 是不是也是 $u$ 的出点，如果是的话则答案加一，它的时间复杂度为每个点的入度与出度之积的和。

然后我们考虑把点权赋为其在原图上的度，这样时间复杂度就是 $O(m \sqrt m)$。

具体证明，考虑两种点：入度 $< \sqrt m$ 的以及入度 $\ge \sqrt m$ 的。

对于入度 $< \sqrt m$ 的，这样的点的出度总和 $\le m$，总贡献为 $O(m \sqrt m)$；

对于入度 $\ge \sqrt m$ 的，这类点至多只有 $\sqrt m$ 个，所以每个点的出度都 $\le \sqrt m$，这样的点入度总和为 $m$，总贡献也为 $O(m \sqrt m)$。

所以，时间复杂度为 $O(m \sqrt m)$。

模板题代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100001, M = 200001;bool vis[N];
int n, m, d[N], u[M], v[M], ans;vector<int> to[N];
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= m;i ++) scanf("%d%d", &u[i], &v[i]), d[u[i]] ++, d[v[i]] ++;
	for (int i = 1;i <= m;i ++){
		if (d[u[i]] > d[v[i]] || (d[u[i]] == d[v[i]] && u[i] > v[i])) swap(u[i], v[i]);
		to[u[i]].push_back(v[i]);
	}
	for (int u = 1;u <= n;u ++){
		for (int v : to[u]) vis[v] = 1;
		for (int v : to[u]) for (int x : to[v]) ans += vis[x];
		for (int v : to[u]) vis[v] = 0;
	}printf("%d", ans);
}