@ 的题解

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

$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;
}

先考虑一个简单的暴力，$O(n^3)$ 去枚举每一个点，然后找是否有三元环，最后答案除以 $6$。

发现这样统计会有大量无用的和重复的，考虑去掉这些重复的。

如果将无向图换成有向图，那样就没有重复了。

给每个点一个权值，权值大的向权值小的连边，这样就不会有三元环没有被统计了。

考虑统计时每个三元环都是最大的连向两个小的，小的中大的向小的连边。

然后考虑权值，由于后面要枚举每个点的每条边，所以度数小的边权值大，度数相同的编号小的权值大。

直接暴力判断即可。

时间复杂度 $m\sqrt m$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,vis[N],rd[N],ans;
vector<int> e[N];
struct Edge{int x,y;}a[N];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y),rd[a[i].x]++,rd[a[i].y]++;
    for(int i=1;i<=m;i++){
        if(rd[a[i].x]<rd[a[i].y]) e[a[i].x].push_back(a[i].y);
        else if(rd[a[i].x]>rd[a[i].y]) e[a[i].y].push_back(a[i].x);
        else e[min(a[i].x,a[i].y)].push_back(max(a[i].x,a[i].y));
    }
    for(int i=1;i<=n;i++){
        for(int j:e[i])vis[j]=i;
        for(int j:e[i])
            for(int k:e[j])if(vis[k]==i)ans++;
    }
    printf("%d",ans);
    return 0;
}