无向图求三元环的个数

原文链接

它实际上是想始终保证复杂度为m×根号m，也就是保证枚举的边数尽可能小于根号m。所以判断一下，小于根号m直接可以进行下一个点的枚举就像dfs深搜一样，如果大了，我们不继续，而是从最初点上枚举别的就像bfs广搜一样

代码：

/*
*  无向图求三元环
*/
 
#include<cstdio>
#include<vector>
#include<unordered_set>
#include<cmath>
 
using namespace std;
 
typedef long long ll;
 
const int maxn=1e5+10;
 
vector<int> g[maxn];
unordered_set<ll> st;
 
int vis[maxn],link[maxn],out[maxn];
 
int main(){
    ll ans,sum;
    int n,m,x,y,z,B;
    while(scanf("%d%d",&n,&m)!=EOF){
        B=sqrt(m);
        st.clear();
        for(int i=1;i<=n;i++){
            g[i].clear();
            vis[i]=link[i]=out[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            out[x]++;
            g[y].push_back(x);
            out[y]++;
            st.insert((ll)n*x+y);   //对于大于根号下m的边不好这样进行判断时候有边相连，速度快而且更加家简便
            st.insert((ll)n*y+x);
        }
        ans=0;
        for(int i=1;i<=n;i++){
            x=i;
            vis[x]=1;
            for(int j=0;j<g[x].size();j++){
                link[g[x][j]]=x;
            }
            for(int j=0;j<g[x].size();j++){
                sum=0;
                y=g[x][j];          //枚举第二个点，第一条边
                if(vis[y]) continue;
                if(out[y]<=B){
                    for(int k=0;k<g[y].size();k++){
                        z=g[y][k];
                        if(link[z]==x) sum++;
                    }
                }else{
                    for(int k=0;k<g[x].size();k++){
                        z=g[x][k];
                        if(st.find((ll)z*n+y)!=st.end()) sum++;
                    }
                }
                ans+=sum;
            }
        }
        printf("%lld\n",ans/3);
    }
    return 0;
}