GraphRGB

2 secs 1024 MB

解説

頂点Gに注目します。R -> G および G -> B という経路を見つけることが目標となります。したがって、各頂点Gに隣接する頂点Rの数を $x$ 、頂点Bの数を $y$ とします。各頂点Gについて、 $x \times y$ の値をすべて合計すると、求める経路の数になります。

この解法での計算量は各頂点に隣接する全ノードを探索する事から計算量は $O(N+M)$ となります。