きままにものづくり

日々の気付いたことなんかを書いてます。

SRM618Div1Easy

問題

サイズN(N \leq 100)のグラフが与えられる。各ノードは2つの親を持つか、何も持たないかである。全ての親の性別が男性と女性で分けられる場合は、グラフはFamily treeとなる。与えらたグラフがFamily treeかどうか判別せよ。

解法

二部グラフ判定を行うことで、答えを求めることができる。

計算量

O(N)

コード

広告を非表示にする