题解 | 统计个数

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

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<set<int>> dot(n + 1);
        int m;
        cin >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            dot[a].insert(b);
            dot[b].insert(a);
        }
        int q = 0, p = 0;
        for (int i = 1; i <= n; i++) {
            for (auto it = dot[i].begin(); it != dot[i].end(); it++) {
                for (auto it1 = next(it); it1 != dot[i].end(); it1++) {
                    if (dot[*it].find(*it1) != dot[*it].end()) p++;
                    q++;
                }
            }
        }
        if (p == 0) cout << "0/1\n";
        else {
            int gc = gcd(p, q);
            cout << p / gc << '/' << q / gc << '\n';
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

直接遍历一个点的所有相邻点，若两个相邻点之间有连线，则三角形的个数与线的个数都+1，否则只有线的个数+1