noshi91のメモ

2018/06/16 ライブラリの変更に伴い、コードを書き直しました。 概要 二部グラフ判定の方法を調べるとBFS/DFSが良く出てくるのですが、UnionFindTreeと頂点拡張を用いた方法が簡潔で使いやすいと感じたため覚え書きを兼ねて書きます。 アルゴリズム 全ての頂点についてそれぞれ２つの頂点を用意します。これは一方が「その…