题目概述

给出一张无向图，求 $4$ 个点构成两个有公共边的三元环的方案数。

解题报告

填坑填坑，如果我们知道每条边所在的三元环个数 $num_i$ ，那么 $\sum_{i=1}^{m}{num_i\choose 2}$ 就是答案。

问题是怎么求三元环个数，朴素暴力肯定不行，但是很明显我们可以对度数进行阈值优化，就可以把复杂度降到 $O(m\sqrt m)$ 了，不过这样常数巨大（度数总和是 $2m$ ）。

还有种比较好的方法：给无向边定向，从度数小的连向度数大的（度数相同看编号），然后每次枚举一条边，枚举这条边两个端点出去的点，如果有相同的点就找到了三元环。由于是从度数小的连向度数大的点，所以不会有环（即每个三元环只统计到一遍），并且每个点的出度不超过 $\sqrt m$ ，复杂度也是 $O(m\sqrt m)$ ，但是常数小。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=200000;

int n,m,X[maxm+5],Y[maxm+5],d[maxn+5],pt[maxn+5],ti,vis[maxn+5],num[maxm+5];
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5],w[maxm+5];LL ans;

#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    while (~scanf("%d%d",&n,&m)){
        E=0;for (int i=1;i<=n;i++) lnk[i]=0,d[i]=0;
        for (int i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]),d[X[i]]++,d[Y[i]]++,num[i]=0;
        for (int i=1;i<=m;i++) d[X[i]]>d[Y[i]]||d[X[i]]==d[Y[i]]&&X[i]>Y[i]?Add(Y[i],X[i],i):Add(X[i],Y[i],i);
        for (int i=1;i<=m;i++){
            ti++;for (int j=lnk[X[i]];j;j=nxt[j]) pt[son[j]]=w[j],vis[son[j]]=ti;
            for (int j=lnk[Y[i]];j;j=nxt[j]) if (vis[son[j]]==ti) num[w[j]]++,num[pt[son[j]]]++,num[i]++;
        }ans=0;for (int i=1;i<=m;i++) ans+=(LL)num[i]*(num[i]-1)>>1;printf("%lld\n",ans);
    }return 0;
}