cnblogs 笔记咕咕了半年了……
根号分治的应用。很巧妙。
首先这题不难想到暴力枚举两条邻边做到 \(\mathrm{O}(m^2)\)。然后考虑优化这个东西。
观察到一般的实现方式是枚举点的一条边，然后考虑这条边另一个节点的出边。于是考虑给边赋一个方向使其变成有向图且出度较小。
考虑这样一种连边方式：从度较小的点连到度较大的点，若相同则从编号小的点连到编号大的点。这样每个点的出度为 \(\mathrm{O}(\sqrt m)\) 的。
证明：
- 若一个点的出度小于 \(\mathrm{O}(\sqrt m)\)，则其出度也小于 \(\mathrm{O}(\sqrt m)\)。
- 否则，出度大于这个节点的数量不大于 \(\mathrm{O}(\sqrt m)\)。
然后模拟这个东西就行了。
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define llong long long
#define N 100005
#define M 200005
using namespace std;
using namespace __gnu_pbds;#define bs (1<<20)
char buf[bs], *p1 = buf, *p2 = buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
inline int read(){int x = 0, w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();return x*w;
}typedef pair<int, int> Edge;
Edge G[M];
int to[M], nxt[M], head[N], gsiz;
#define mkarc(u,v) (++gsiz, to[gsiz]=v, nxt[gsiz]=head[u], head[u]=gsiz)
gp_hash_table<int, bool> vis[N];
int deg[N];
int n, m, ans;int main(){n = read(), m = read();for(int i = 1; i <= m; ++i){G[i] = {read(), read()};++deg[G[i].first];++deg[G[i].second];}for(int i = 1; i <= m; ++i){int u = G[i].first, v = G[i].second;if(deg[u]>deg[v] || (deg[u]==deg[v]&&u>v)) swap(u, v);mkarc(u, v);vis[u][v] = true;}for(int u = 1, u <= n; ++u){for(int i = head[u]; i; i = nxt[i]){int v = to[i];for(int j = head[v]; j; j = nxt[j])if(vis[u][to[j]]) ++ans;}}printf("%d", ans);return 0;
}