三元环计数（HDU 6104）

作者：很楠不爱3 | 2024-02-06 21:32:32

踩

竞赛图三元环计数

三元环计数

这个三元环计数就是去计算图里面有多少个三元环。计算这个数目在有的题目里面有很重要的作用。看了一些博客后总结一下。有错误望指正

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\n",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))$ 。下面是一些学习博客，可以看看。