题目背景
无向图 G 的三元环指的是一个 G 的一个子图 G0 ,满足 G0 有且仅有三个点 u,v,w,有且仅有三条边(u,v),(v,w),(w,u)。两个三元环 G1 ,G2 不同当且仅当存在一个点 u,满足 u∈G1 且u不属于G2。

题目描述
给定一个 n 个点 m 条边的简单无向图,求其三元环个数。

输入格式
每个测试点有且仅有一组测试数据。

输入的第一行是用一个空格隔开的两个整数,分别代表图的点数 n 和边数 m。

第 2 到第 (m+1) 行,每行两个用空格隔开的整数 u,v,代表有一条连接节点 u 和节点 v 的边。

输出格式
输出一行一个整数,代表该图的三元环个数。

输入输出样例
输入 #1 复制
3 3
1 2
2 3
3 1
输出 #1 复制
1
输入 #2 复制
5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4
输出 #2 复制
5
说明/提示
【样例 2 解释】

共有 55 个三元环,每个三元环包含的点分别是{1,2,4},{2,3,4},{2,3,5},{2,4,5},{3,4,5}。

【数据规模与约定】

1≤n≤105
1≤m≤2×105
1≤u,v≤n,给出的图不存在重边和自环,但不保证图连通。

给无向图定向,可以证明这样的时间复杂度是O(m sqrt(m))的,具体证明见笔记本。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=200100;
int head[maxn],ver[maxn],nt[maxn],tot=0;
int d[maxn],x[maxn],y[maxn],ha[maxn];

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        d[x[i]]++,d[y[i]]++;
    }
    for(int i=1;i<=m;i++)
    {
        if(x[i]>y[i]) swap(x[i],y[i]);
        if(d[x[i]]<=d[y[i]]) add(x[i],y[i]);
        else add(y[i],x[i]);
    }
    int ans=0;
    for(int x=1;x<=n;x++)
    {
        for(int i=head[x];i;i=nt[i])
            ha[ver[i]]=x;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            for(int k=head[y];k;k=nt[k])
                if(ha[ver[k]]==x) ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}