无向图三元环计数

小知识点，但不可不学。

定义一个优先级：(u<v) 当且仅当 1. (deg[u]<deg[v]) 2. (deg[u]=deg[v]) 且 (u<v)
给无向图中每条边定向，从优先级低连向优先级高，从而图变成 DAG。
不重不漏地暴力统计三元环：原图中的三元环在新图中一定是，枚举 (u)，再枚举 (u) 的出边中的 (v)，再对于每一个 (v) 的指向的点 (O(1)) 判断 (w) 是否被 (u) 指向。
时间复杂度 (O(msqrt m))，可以用根号分治证明：

那么考虑对于每一条边 (lang u rightarrow vrang)，它对复杂度造成的贡献是 (out_v)，因此总复杂度即为 (sum_{i = 1}^m out_{v_i})，其中 (v_i) 是第 (i) 条边指向的点，(out_v) 是点 (v) 的出度。
考虑分情况讨论。

当 (v) 在原图（无向图）上的度数不大于 (sqrt m) 时，由于新图每个节点的出度不可能小于原图的度数，所以 (out_v = O(sqrt m))。
当 (v) 在原图上的度数大于 (sqrt m) 时，注意到它只能向原图中度数不小于它的点连边，又因为原图中所有的点的度数和为 (O(m))，所以原图中度数大于 (sqrt m) 的点只有 (O(sqrt m)) 个。因此 (v) 的出边只有 (O(sqrt m)) 条，也即 (out_v = O(sqrt m))。

因此所有节点的出度均为 (O(sqrt m))，总复杂度 (sum_{i = 1}^m out_{v_i} = O(m sqrt m))。
——扶苏's Blog

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,ans,u[N],v[N],deg[N],bk[N];
vector<int>G[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&u[i],&v[i]),deg[u[i]]++,deg[v[i]]++;
	for(int i=1;i<=m;i++){
		if(deg[u[i]]>deg[v[i]]||deg[u[i]]==deg[v[i]]&&u[i]>v[i])swap(u[i],v[i]);
		G[u[i]].push_back(v[i]);
	}
	for(int x=1;x<=n;x++){
		for(int i=0;i<G[x].size();i++)bk[G[x][i]]=1;
		for(int i=0;i<G[x].size();i++)for(int j=0;j<G[G[x][i]].size();j++)ans+=bk[G[G[x][i]][j]];
		for(int i=0;i<G[x].size();i++)bk[G[x][i]]=0;
	}
	cout<<ans;
}