题解 | 统计个数

三角形的前提是线。对每个点进行深度为2的dfs就好了，当深度等于2时意味着构成一条线。然后判断线的末尾与起点之间是否有连边即可，用来更新三角形的个数。

#include<bits/stdc++.h>
using namespace std;
int n, m, gx[205][205], ecnt, tcnt;
vector<int> g[205];
int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b, a%b);
}
void fill(int x, int dep, int fa, int cen) {
    if(dep==2) {
        ecnt++;
        if(gx[x][cen]) tcnt++;
        return;
    }
    for(auto &ele: g[x]) {
        if(ele!=fa) fill(ele, dep+1, x, cen);
    }
}
void solve() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        g[i].clear();
        for(int j=1; j<=n; j++) {
            gx[i][j]=0;
        }
    }
    for(int i=1; i<=m; i++) {
        int u, v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        gx[u][v]=gx[v][u]=1;
    }
    ecnt=tcnt=0;
    for(int i=1; i<=n; i++) {
        fill(i, 0, 0, i);
    }
    if(tcnt==0) ecnt=1;
    cout<<tcnt/gcd(tcnt, ecnt)<<'/';
    cout<<ecnt/gcd(tcnt, ecnt)<<'\n';
}
int main() {
    int T; cin>>T; while(T--) solve();
}