简要题意：
给定 \(n\) 个点 \(m\) 条边的无向图，求其三元环个数。
\(n \leq 10^5 , m \leq 2 * 10^5\).
首先考虑一个暴力做法。
其实我们就是要寻找有多少组 \((u,v,w)\) 能使同时存在三条边 \(u \leftrightarrow v , u \leftrightarrow w , v \leftrightarrow w\).
于是我们可以暴力枚举一条边 \(u \leftrightarrow v\)，并找它们连边的公共点 \(w\) 的个数。
复杂度显然，\(\mathcal{O}(m^2)\).
对于重复问题，我们可以考虑，只枚举 \(u < v\) 的边，然后将答案 \(\div 3\).
但实际上，对于暴力做法，我们应该考虑，如何减少需要计算的边的数量。
不妨从对重复问题的处理入手，是否可以只考虑 \(\text{deg}(u) < \text{deg}(v)\) 的边？（其中 \(\text{deg}(x)\) 表示 \(x\) 的度）
显然，只要我们能明确任意一个全序，那么都不会影响答案的正确性。于是对于 \(u\) 和 \(v\)，只考虑：
\[\text{deg}(u) < \text{deg}(v) \space 或者 \space \text{deg}(u) = \text{deg}(v) \& u < v \]的边。建新图。
这样能否减少合法边的数量呢？答案是肯定的。
对于度 \(\leq \sqrt{m}\) 的点，那么我们直接在新图上暴力，单点复杂度不超过 \(\sqrt{m}\). 总共不超过 \(m \sqrt{m}\).
对于度 \(> \sqrt{m}\) 的点，那么这样的点最多不超过 \(\sqrt{m}\) 个，同样是新图上暴力，单点复杂度不超过 \(m\)，总共仍然是 \(m \sqrt{m}\).
时间复杂度：\(\mathcal{O}(m \sqrt{m})\).
注意到，暴力的时候请对 \(u\) 的点打标记，而不是每次暴力扫一边，或者每一个用 find。实测洛谷暴力或用 find 无法通过，而打标记的小优化可以通过。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
inline int read() {
char c=getchar(); int f=1,x=0;
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
return x*f;
}
struct data {
int u,v;
} e[N];
int n,m,deg[N],ans=0;
vector <int> G[N];
bool vis[N];
int main() {
n=read(),m=read();
for(int i=1;i<=m;i++) {
int u=read(),v=read();
deg[u]++; deg[v]++;
e[i].u=u; e[i].v=v;
}
for(int i=1;i<=m;i++)
if(deg[e[i].u] < deg[e[i].v] || (deg[e[i].u] == deg[e[i].v] && e[i].u < e[i].v)) G[e[i].u].push_back(e[i].v);
else G[e[i].v].push_back(e[i].u) , swap(e[i].v,e[i].u);
for(int i=1;i<=m;i++) {
int u = e[i].u , v = e[i].v;
for(int i=0;i<G[u].size();i++) vis[G[u][i]] = 1;
for(int j=0;j<G[v].size();j++) ans += vis[G[v][j]];
for(int i=0;i<G[u].size();i++) vis[G[u][i]] = 0;
}
printf("%d\n",ans);
return 0;
}