AtCoder Beginner Contest 262 B問題 Triangle (Easier)
問題
提出解答
問題の概要
頂点
辺の単純無向グラフ
が与えられる. ただし,
である.
この にある三角形の個数を求めよ. なお, 三角形とは相異なる
個の頂点
であって,
であるときの長さ
のサイクル
である.
制約
は単純グラフ.
解法
相異なる3頂点 の取り方は
通りである. ここで,
であるから,
である. よって, 相異なる3頂点 の取り方は
通り以下である. そして,
であるかは定数時間で判定できる.
従って, 相異なる3頂点 取り方全てに対して,
であるかどうかを判定し,
となった3頂点の組
が答えになる. 計算量は
時間である.