luogu P1989 无向图三元环计数

https://www.luogu.com.cn/problem/P1989

经典问题，
对于原图的每一条边$u?>v$，如两点的度数不一样，那么就度数小的连向度数大的，否则编号小的连向编号大的
然后考虑新图的每一条边$u?>v$遍历和$v$相连的每个点$w$,看$w$是否和$u$相连，不难发现这个的时间复杂度是$\sum out[v_i]$的

那么如何证明这个时间复杂度是$O(m\sqrt{m})$的呢？

考虑原图的一个点$u$,如果$deg[u]\le \sqrt{m}$,显然出度$\le \sqrt{m}$
如果$deg[u]>\sqrt{m}$,因为只能向度数比$u$大的点$v$连边，然而$v$的个数显然是不超过$\sqrt{m}$个的,所以显然正确

code:

#include<bits/stdc++.h>
#define N 2000050
using namespace std;
int n, m, in[N], vis[N];
vector<int> g[N];
struct E {
    int u, v;
} e[N << 1];
int main() {
    scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &e[i].u, &e[i].v);in[e[i].u] ++, in[e[i].v] ++;}for(int i = 1; i <= m ; i++) {
    int u = e[i].u, v = e[i].v;if(in[u] > in[v]) swap(u, v);if((in[u] == in[v]) && u > v) swap(u, v);g[u].push_back(v);}int ans = 0;for(int u = 1; u <= n; u ++) {
    for(int v : g[u]) vis[v] = u;for(int v : g[u])for(int w : g[v])if(vis[w] == u) ans ++;}printf("%d", ans);return 0;
}