Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 262 B問題 Triangle (Easier)

AtCoder ABC ABC262 B問題 200 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ が与えられる. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{U_j V_j \mid j=1,2, \dots, M\}$

である.

この $G$ にある三角形の個数を求めよ. なお, 三角形とは相異なる $3$ 個の頂点 $u,v,w \in V$ であって, $uv,vw,wu \in E$ であるときの長さ $3$ のサイクル $u,v,w$ である.

制約

$3 \leq N \leq 1000$
$1 \leq M \leq \frac{N(N-1)}{2}$
$1 \leq U_j \lt V_j \leq N$
$G$ は単純グラフ.

解法

相異なる3頂点 $u,v,w \in E$ の取り方は $\frac{N(N-1)(N-2)}{6}$ 通りである. ここで, $N \leq 100$ であるから,

$\dfrac{N(N-1)(N-2)}{6} \leq \dfrac{N^3}{6} \leq N^3=10^6$

である. よって, 相異なる3頂点 $u,v,w \in E$ の取り方は $10^6$ 通り以下である. そして, $uv,vw,wu \in E$ であるかは定数時間で判定できる.

従って, 相異なる3頂点 $u,v,w \in E$ 取り方全てに対して, $uv,vw,wu \in E$ であるかどうかを判定し, $uv,vw,wu \in E$ となった3頂点の組 $(u,v,w)$ が答えになる. 計算量は $O(N^3)$ 時間である.