三元环计数

算法如其名，就是用来找三元环的。

介绍

给出一张无向图，问图中有多少个三元组 { x , y , z } \{x,y,z\} {x,y,z}，满足图中存在 { x − y , y − z , z − x } \{x-y,y-z,z-x\} {x−y,y−z,z−x} 三条边。

转化

考虑将这张图转化为有向图：对于一条无向边 $x-y$，不妨设点 $x$ 的度大于点 $y$ 的度，那么就将这条无向边变成 $x\to y$。假如两点的度相同，就从编号大的往编号小的连边。

这样转化后，这张图一定是有向无环图。

证明：

使用反证法，假设有一个环：$a\to b\to c\to a$，那么有（设 $x$ 的度为 $d_x$）：$d_a\ge d_b\ge d_c\ge d_a$，要使该不等式成立，当且仅当满足 $d_a=d_b=d_c=d_a$。

设 $x$ 的编号为 $i{d}_x$，那么有：$i{d}_a>i{d}_b>i{d}_c>i{d}_a$，即 $i{d}_a>i{d}_a$，该柿子不成立，故假设不成立，证毕。

求解

步骤如下：

1. 枚举每一个点，对于当前的点，将它能到达的点做上标记
2. 做完标记后，枚举每个被做过标记的点，对于当前被做过标记的点，枚举他能到达的点
3. 假如这个能到达的点是被做过标记的，那么就找到了一个三元环，答案$+1$

正确性

转化完后，每一个三元环会变成下面这样的东西：

只有枚举到红点的时候，这个三元环才会被计算到，这就保证了不会重复计算并且不会漏算。

时间复杂度

考虑每一条边被遍历的次数：对于一条边 $x\to y$，他被遍历的次数为 $i{n}_x$。（$i{n}_x$表示 $x$ 的入度），那么总的时间复杂度就是每一条边的 $i{n}_x$ 之和。

又可以发现，$i{n}_x$ 的上限就是 $\sqrt{m}$，因为要求每个连向 $x$ 的点的度都大于 $i{n}_x$，也就是说，有 $i{n}_x$ 个点的度大于 $i{n}_x$，这样就至少需要 $i{n}_x^2$ 条边，所以 $i{n}_x^2\le m\Rightarrow i{n}_x\le \sqrt{m}$。

例题

题目传送门

显然，题目中要求的四元组，也就是两个有一条公共边的三元环拼在一起，那么求出每条边在多少个三元环中（设 $to{t}_i$ 表示第 $i$ 条边在多少个三元环里），然后 ${\sum }_{i=1}^m{C}_{to{t}_i}^2$ 就是答案。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 300010
#define ll long long

int n,m;
struct edge{int y,next;};
edge e[maxn*4];
int len;
int first[maxn];
void buildroad(int x,int y)
{
	e[++len]=(edge){y,first[x]};
	first[x]=len;
}
struct node{int x,y;};
node edges[maxn*2];
int du[maxn],id[maxn],to[maxn],tot[maxn];
inline ll C(int x){return (ll)x*(x-1)/2ll;}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		memset(du,0,sizeof(du));//记录每个点的度的数组
		for(int i=1;i<=m;i++)
		scanf("%d %d",&edges[i].x,&edges[i].y),du[edges[i].x]++,du[edges[i].y]++;
		memset(first,0,sizeof(first));len=0;
		for(int i=1,x,y;i<=m;i++)
		{
			x=edges[i].x,y=edges[i].y;
			if(x>y)swap(x,y);//让x成为编号小的点
			if(du[x]>=du[y])buildroad(x,y);//度大的往小的连有向边
			else buildroad(y,x);
		}
		memset(tot,0,sizeof(tot));//别忘了初始化各种数组
		memset(to,0,sizeof(to));//to[i]表示当前点到点i的边是第几条边
		memset(id,0,sizeof(id));//id表示每个点的标记
		for(int i=1;i<=n;i++)
		{
			int x=i;
			for(int j=first[x];j;j=e[j].next)//枚举能到达的点，给他们大商标机
			id[e[j].y]=x,to[e[j].y]=j;//打标记，记录to
			for(int j=first[x];j;j=e[j].next)//再次遍历所有有标记的点
			{
				for(int k=first[e[j].y];k;k=e[k].next)//遍历有标记的点能到达的点
				if(id[e[k].y]==x)tot[j]++,tot[k]++,tot[to[e[k].y]]++;
				//假如能到达一个有标记的点，那么就找到了一个三元环，给这三条边都打上标记
			}
		}
		ll ans=0;
		for(int i=1;i<=len;i++)//统计答案
		ans+=C(tot[i]);
		printf("%lld\n",ans);
	}
}