三元环计数
这个三元环计数就是去计算图里面有多少个三元环。计算这个数目在有的题目里面有很重要的作用。看了一些博客后总结一下。有错误望指正
1. 三元环
三元环就是图中所示的样子
2.如何判断是三元环？
三元环现实中我们一下就可以判断出来，但是竞赛中要怎么判断呢？？
我们都知道一句话：敌人的敌人就是我们的朋友 ，对三元环的判断基本就是这样的。如果我们知道a b间连边，b c间连边，只要根据a c之间是否连边就可以判断这三个点能不能构成三元环。
3.具体做法：
上面的只是抽象的理解，具体的做法如下：（不着急我们一步一步来）
**(1) 只看如上图三点 : **
- 如果只看上面三点的话，第一步就是标记a访问过（vis[a]=1）。并将与 a 所连的所有点的前置点指向a（即 pre[b]=a ,pre[c]=a ）。
- 遍历与a相连的所有点，假设先遍历到b，再遍历b的所有相连的点这里是c，这样我们相当于确定a为自己，b为自己的敌人，c为b的敌人，其实这个比喻不太恰当，判断三点能不能构成三元环主要看a c是否连边（即看pre[c]是否等于a ）。发现pre[c]==a,所以cnt++( cnt记录三元环个数)。
- 之后重复对每个点进行操作。
(2)多个点：
-
原理就是上面的，具体做法见下面。
-
首先要做一些准备工作，记录每个点的入度，还有hash (用于之后操作的判断连点是否相连) ，将所有的点分为两类 ： 1. 入度 (<=sqrt(m)) 的点 2. 入度(>sqrt(m)) 的点（这一步只需要一个if判断就好了）。
-
做完上面的准备我们就可以遍历图中每一个点让它作为a点， 然后遍历它的所有相连的点设为b,赋值pre[edge[a] [i]]=a(即这个点与a连边), 对于所有b点，
-
如果是第一类点就像（1）中那样处理，具体见代码会好理解点。因为mm条边最多每条边遍历一次，然后暴力的点的入度<=sqrt(m)<=sqrt(m)，所以复杂度 O(msqrt(m))。
-
如果是第二类点就直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过sqrt(m)sqrt(m)个，所以复杂度约为O(sqrt(m)3) = O(msqrt(m))。
下面是第二类点暴力判三点的方法：
-
-
至于上面如何判断三点构成环可以map，hash, set都可以,这里我用set（具体操作也是映射的原理），如果u,v两点之间连边那么set里面就添加 1ll * u *bas+v , 和 1ll * v * bas + u ( 这里bas=1e5+1)。判断时就是，现在我们不是有a,b两点对吧，然后b度数较大用第二种方法，这时我们遍历与a相连的所有点c，根据前面的描述肯定ab,ac之间连边了，那么现在只要判断bc之间是否连边就可以判断三点是否构成三元环 (具体即_ hash.find(1ll * b * bas+c) != _ hash.end() ) ,这里_hash即set名，也就是只要再set集合中找的到两点hash的值就说明里连边了。
-
如何满足就ans++。具体学习见代码（HDU 6184）
HDU 6184 题目：
给一张n个点m条边的无向图，问有多少个A−structureA−structure
其中A−structureA−structure满足V=(A,B,C,D)V=(A,B,C,D) && E=(AB,BC,CD,DA,AC)E=(AB,BC,CD,DA,AC) 显然A−structureA−structure是由两个有公共边的三元环构成的
对于这道题，我们在求三元环的时候，统计一下每条边有多少对点能构成三元环，C(cnt,2)C(cnt,2)累计一下即可
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MA=1e5+5;
const int bas=1e5+1;
vector<int>edge[MA];//邻接表存图
set<ll>_hash;//set集合
int n,m;
int vis[MA],du[MA],pre[MA];//分别维护：是否处理过标记，度数，所连点
void init()//初始化
{
for(int i=1;i<=n;++i){
vis[i]=du[i]=pre[i]=0;
edge[i].clear();
}
}
void woke()
{
int x=sqrt(1.0*m);//这就是两类点的区分点sqrt(m)
ll ans=0,cnt;//分别维护答案和每次的三元环个数
for(int a=1;a<=n;++a){//遍历每一个点作为a
vis[a]=1;
for(int i=0;i<edge[a].size();++i)//见步骤3
pre[edge[a][i]]=a;
for(int i=0;i<edge[a].size();++i){
cnt=0;
int b=edge[a][i];
if(vis[b])continue;
if(du[b]<=x){//第一类点的处理
for(int j=0;j<edge[b].size();++j){
int c=edge[b][j];
if(pre[c]==a) ++cnt;//就是三个点时的判断方法
}
}
else{//第二类点的处理
for(int j=0;j<edge[a].size();++j){
int c=edge[a][j];
if(_hash.find(1ll*b*bas+c)!=_hash.end()) ++cnt;//暴力判三点的方法
}
}
ans+=(cnt-1)*cnt/2;
}
}
printf("%lld
",ans);
}
int main()
{
int u,v;
while(~scanf("%d%d",&n,&m)){
init();
_hash.clear();
for(int i=1;i<=m;++i){//准备
scanf("%d%d",&u,&v);
du[u]++,du[v]++;//记录度数
edge[u].push_back(v);//存图
edge[v].push_back(u);
_hash.insert(1ll*u*bas+v);//存相连状态（hash思想）
_hash.insert(1ll*v*bas+u);
}
woke();
}
return 0;
}
还有一些其他方法基本就是在优化，这个方法复杂度(O(msqrt(m))) 。下面是一些学习博客，可以看看。