閉路の偶奇

グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。
今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。
全然今まで気付かなかったのですが
「偶数長の閉路しかない⇔2部グラフ」
です。あとはこれより、2部グラフかどうかさえ判定できればいいです。
これは簡単ですね。
(追記)多重辺、ループのない時です

Problem - 557D - Codeforces