题解 | 统计个数

import math
import sys

data = sys.stdin.read().split()
t = int(data[0])
index = 1
for _ in range(t):
    n = int(data[index])
    m = int(data[index+1])
    index += 2

    # 初始化数据结构,set()提供o(1)的查找，方便查看某两个点是否连接
    graph = [set() for _ in range(n+1)]

    # 构建图
    for i in range(m):
        u, v = int(data[index]), int(data[index+1])
        graph[u].add(v)
        graph[v].add(u)
        index += 2

    # 计算以枚举点为中心的线的数量(实际上就是计算C(n,2)，n为邻居个数)
    lines = 0
    for i in range(1, n + 1):
        deg = len(graph[i])
        lines += deg * (deg - 1) // 2

    # 计算三角的数量（每个三角会被记录3次，刚好满足题目p为3倍的三角数量）
    triangles = 0
    for i in range(1, n + 1):
        neighbors = list(graph[i])
        for j in range(len(neighbors)):
            for k in range(j + 1, len(neighbors)):
                if neighbors[k] in graph[neighbors[j]]:
                    triangles += 1

    # 计算最简分数
    p = triangles
    q = lines

    if p == 0:
        print("0/1")
    else:
        # 约分，直接 math.gcd() 获取最大公因子
        g = math.gcd(p, q)
        p //= g
        q //= g
        print(f"{p}/{q}")

“线”的定义题目属于是没描述清楚，直接说3个不同的点连接且不成环则构成一条“线”更好，不然以为在求无环连通块的数量

差点给自己绕进去了，还想着创建个集合的集合储存所有有效的三角（三个顶点），实际上，由于判断3角是从当前点为顶点的视角判断的，固一个三角一定会被判断3次，所以题目才会设定 p=3倍三角个数