题解 | 统计个数

用二维vector存储图的边关系。

1. 线的统计：通过三层循环遍历所有有序三元组 (a,b,c)，满足 a-b 且 b-c 相连时计数，最后除以 2 去重。
2. 三角的统计：遍历无序三元组 (a,b,c)（a<b<c），确保三者两两相连时计数，避免重复。

#include <iostream>
#include<vector>
using namespace std;

int gcd(int a,int b){
    while(b){
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<bool>>adj(n+1,vector<bool>(n+1,false));
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        adj[a][b]=true;
        adj[b][a]=true;
    }
    int line_cnt=0;
    for(int a=1;a<=n;a++){
        for(int b=1;b<=n;b++){
            if(a==b||(!adj[a][b]))continue;
            for(int c=1;c<=n;c++){
                if(c==a||c==b||(!adj[b][c]))continue;
                line_cnt++;
            }
        }
    }
    line_cnt/=2;
    int triangle_cnt=0;
    for(int a=1;a<=n;a++){
        for(int b=a+1;b<=n;b++){
            if(!adj[a][b])continue;
            for(int c=b+1;c<=n;c++){
                if(adj[a][c]&&adj[b][c])triangle_cnt++;
            }
        }
    }
    int p=3*triangle_cnt,q=line_cnt;
    if(p==0)cout<<"0/1\n";
    else{
        int g=gcd(p,q);
        cout<<p/g<<'/'<<q/g<<endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}