📝 题目大意

给定一个 $N$ 个顶点 $M$ 条边的简单无向图，统计图中三元环（三角形）的数量，即满足 $1 \leq a < b < c \leq N$ 且 $(a,b)$、$(b,c)$、$(c,a)$ 之间均有边相连的三元组个数。

💡 解题思路

1. 题目分析：$N \leq 100$，数据规模很小，可以直接暴力枚举所有三元组。$M$ 最大为 $\frac{N(N-1)}{2}$，图是简单无向图，没有重边和自环。

2. 算法推导：

   • 使用邻接矩阵 g[u][v] 存储边的关系，方便 $O(1)$ 查询任意两点是否相连。
   • 枚举所有满足 $a < b < c$ 的三元组 $(a, b, c)$，检查 $g[a][b]$、$g[b][c]$、$g[c][a]$ 是否均为 true。
   • 每找到一个合法三元组，计数器 ans 加一。

3. 边界与细节：

   • 顶点编号从 $1$ 开始，矩阵大小开 $(N+1) \times (N+1)$ 避免越界。
   • 枚举时 $a$ 从 $1$ 到 $N$，$b$ 从 $a+1$ 到 $N$，$c$ 从 $b+1$ 到 $N$，严格保证 $a < b < c$，避免重复计数。
   • 无向图每条边需双向标记：g[u][v] = g[v][u] = true。

⏱️ 复杂度分析

• 时间复杂度：$O(N^3)$，枚举所有三元组需要 $\binom{N}{3} \approx \frac{N^3}{6}$ 次检查，$N=100$ 时约 $1.6 \times 10^5$，完全可行。
• 空间复杂度：$O(N^2)$，邻接矩阵存储所有点对关系。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    // 邻接矩阵，g[i][j] 表示顶点 i 和 j 之间是否有边
    vector<vector<bool>>g(N+1,vector<bool>(N+1,false));
    for(int i=0;i<M;i++) {
        int u,v;
        cin>>u>>v;
        g[u][v]=g[v][u]=true;  // 无向图，双向标记
    }
    int ans=0;
    // 三重循环枚举所有满足 a<b<c 的三元组
    for(int a=1;a<=N;a++) {
        for(int b=a+1;b<=N;b++){
            for(int c=b+1;c<=N;c++){
                // 检查三条边是否都存在（即构成三角形）
                if(g[a][b]&&g[b][c]&&g[c][a]){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}