SRM618Div1Easy
問題
サイズN()のグラフが与えられる。各ノードは2つの親を持つか、何も持たないかである。全ての親の性別が男性と女性で分けられる場合は、グラフはFamily treeとなる。与えらたグラフがFamily treeかどうか判別せよ。
解法
二部グラフ判定を行うことで、答えを求めることができる。
計算量
O(N)
サイズN()のグラフが与えられる。各ノードは2つの親を持つか、何も持たないかである。全ての親の性別が男性と女性で分けられる場合は、グラフはFamily treeとなる。与えらたグラフがFamily treeかどうか判別せよ。
二部グラフ判定を行うことで、答えを求めることができる。
O(N)