题解 | 统计个数

解答：题目已经明确说了图论，那么我们直接用邻接矩阵存图即可，这里不用邻接表后面解释。那么二维数组建好图后，直接声明记录线的个数cnt_l和记录三角和线个数cnt_s。直接暴力枚举三次分别对应三个点。最后判断首尾两个点是否相连即可，如果相连那么就cnt_s++，只要进入了三层循环就cnt_l++。

这里没有直接判重，是因为后面会有分式约分的过程，那么直接辗转相除法重复取余找到最大公约数，将两数除去最大公约数即可，那么同时把重复的边也同样除去！

不用邻接表存是因为邻接表不能直接判断首尾是否相连，必须再加一层遍历，可能超时我说的是可能哦~

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector<vector<int>>g(n+1,vector<int>(n+1,0));
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        g[a][b]=1;
        g[b][a]=1;
    }
    int cnt_l=0;
    int cnt_s=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j]!=0){
                for(int k=1;k<=n;k++){
                    if(k!=i&&g[j][k]!=0){
                        cnt_l++;
                        if(g[i][k]!=0){
                            cnt_s++;
                        }
                    }
                }
            }
        }
    }
    if(cnt_s==0){
        cout<<"0/1"<<endl;
        return;
    }
    a=cnt_l;
    b=cnt_s;
    while(b!=0){//辗转相除法求出最大公约数，化简分式
        int t=a%b;
        a=b;
        b=t;
    }
    cnt_l/=a;
    cnt_s/=a;
    cout<<cnt_s<<"/"<<cnt_l<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}