三元环计数问题

link，给定一个无向图，求其中三元环的数量。

$1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$ 。

构造一个这样的有向图：对于原来图中的每一条无向边，改为由度数小的向度数大的连边，若相等则由编号小的向编号大的连边，在这样的图中，三元环 ${ x,y,z}$ ，度数最小或编号最小的点回向另外两点连边，所以边肯定是 $x \rightarrow y$，$x \rightarrow y$，$y \rightarrow z$ 这种形式的。这样枚举 $x$，标记所有 $x$ 出去的点 $y$ ，在枚举这些点出去的点 $z$ ，若 $z$ 被标记了说明构成三元环。

这样的时间复杂度是 $\Theta(m \sqrt m)$，为什么呢？我们枚举 $x$ 出去的 $y$ 相当于枚举了每条边，这是 $\Theta(m)$；枚举 $y$ 后还要枚举 $z$，为什么这个东西的复杂度是 $\Theta(\sqrt m)$ 呢？现在我们要证明每个点的出度不可能大于$\sqrt m$。

反证法，若一个点的出度 $> \sqrt m$，因为一个点只能连向度数大于等于它的点，所以它出去的 $\sqrt m$ 个点出度也都 $> \sqrt m$ 个点，这样两个 $> \sqrt m$ 相乘，总边数就 $> m$，与 $m$ 条边矛盾，因此每个点的初度 $\le \sqrt m$，复杂度就是 $\Theta(m \sqrt m)$ 了。

CODE

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

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 100010
#define M 200010
#define pb push_back

int n, m, x[M], y[M], deg[N], vis[N];
vector<int> e[N];

int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i ++) {
		x[i] = read(), y[i] = read();
		deg[x[i]] ++, deg[y[i]] ++;
	}

	for (int i = 1; i <= m; i ++) {
		if (deg[x[i]] < deg[y[i]] || deg[x[i]] == deg[y[i]] && x[i] < y[i]) e[x[i]].pb(y[i]);
		else e[y[i]].pb(x[i]);
	}

	int res = 0;
	for (int i = 1; i <= n; i ++) {
		for (auto j : e[i]) vis[j] = 1;
		for (auto j : e[i]) for (auto k : e[j]) if (vis[k]) res ++;
		for (auto j : e[i]) vis[j] = 0;
	}

	printf("%d\n", res);
	return 0;
}