问题求解III-HW04 题解
Problem A: 飘雪圣域
给定一张 $n$ 个点 $m$ 条边的图，求图的割点。
求图的割点有著名的时间复杂度为 $O(n+m)$ 的 Tarjan 算法，此处不做赘述。
Problem B: 同色三角形
给定一张 $n$ 个点的完全图，每条边为黑色或白色，问图中有多少个同色三角形。
作为中秋+国庆放假的福利，本题设置的数据范围可以允许最简单的 $O(n^3)$ 枚举算法通过
这里主要讲解非平凡的 $O(n^2)$ 做法应当如何实现；将复杂度优化到平方级需要仔细分析该问题的性质以减少枚举的次数。
枚举同色三角形似乎很难逃出三方枚举的困境——对于每个顶点 $u$，它的任意两条同色边关联的相邻点 $v_1, v_2$ 都需要再检查边 $(v_1, v_2)$ 的颜色。因此我们换一个角度考虑：该图中三角形的总数为 $\binom{n}{3}$，我们只要转而计算图中非同色三角形的数目，就可以算出同色三角形的数目。
另一个重要的观察是：对于任意顶点 $u, v_1, v_2$，如果 $\text{color}(u, v_1)\neq \text{color}(u, v_2)$，那么无论边 $(v_1, v_2)$ 是什么颜色，$(u, v_1, v_2)$ 都一定能形成一个异色三角形。 进一步地，记 $black_u$ 表示 $u$ 的黑色邻边的数目，那么顶点带有 $u$ 的异色三角形数目为 $black_u\cdot (n-1-black_u)$。因此，同色三角形的数目为
$$ ans=\binom{n}{3} - \frac{1}{2}\sum_{u\in V}black_u\cdot (n - 1 - black_u) $$
公式中的 $1/2$ 来源于一个异色三角形会被它的两个“异色邻边顶点”计算两次。