题解 | #K BanG Dream! It's MyGO!!!!!）#
BanG Dream! Its MyGO!!!!!
https://ac.nowcoder.com/acm/contest/89237/K
K Mygo!!!!! python
三芒星，闪电折线比较简单，分别枚举点和枚举边就行
比较复杂的是三角形（三元环）
对于边u -> v，从小打大单向建图，用set储存在g
对于三元环（u，v，w），枚举u和v，则w的情况数是 len(g[u] & g[v])
复杂度大概是 o(mlogm)
from sys import stdin input = lambda: stdin.buffer.readline().rstrip() n, m = map(int, input().split()) g = [set() for _ in range(n)] cnt = [0] * n e = [] for _ in range(m): u, v = sorted(x - 1 for x in map(int, input().split())) cnt[u] += 1 cnt[v] += 1 g[u].add(v) e.append((u, v)) ans1 = sum(len(g[i] & g[j]) for i in range(n - 2) for j in g[i]) ans2 = sum((cnt[i] * (cnt[i] - 1) * (cnt[i] - 2)) // 6 for i in range(n)) ans3 = sum((cnt[u] - 1) * (cnt[v] - 1) for u, v in e) print(ans2 + ans3 - ans1 * 2)
查看3道真题和解析
