二部グラフ判定をUnionFindTreeで行う

2018/06/16 ライブラリの変更に伴い、コードを書き直しました。

概要

二部グラフ判定の方法を調べるとBFS/DFSが良く出てくるのですが、UnionFindTreeと頂点拡張を用いた方法が簡潔で使いやすいと感じたため覚え書きを兼ねて書きます。

アルゴリズム

　全ての頂点についてそれぞれ２つの頂点を用意します。これは一方が「その頂点を赤で塗る」、もう一方が「その頂点を青で塗る」ことを意味しています(2SATのイメージ) 一方をV_a、もう一方をV_bと表記します。
　そして、各辺 u-v について (u_a, v_b), (u_b, v_a) をUnionFindTreeで併合します。これは「uを赤で塗るならvは青、uを青で塗るならvは赤」という真偽の対応関係を示しています。するとこの拡張されたグラフで同じ集合であるならば、その全ての要素の真偽(対応する色に塗られるかどうか)が一致するということになります。
　最後に、各頂点 v に対して v_a と v_b が同じ集合にあるかを判定します。同じ集合に属しているならば、その頂点は塗分けについて矛盾している⇒二部グラフに属していないということを意味します。
　具体的な塗分け等を考えたいときは、真を意味する追加頂点を作ってそれとの連結判定をすると良さそう (もっといいやり方があったら教えてください)

利点

・処理が単純で間違えにくい

・UnionFindTreeを除けばコードが短い

・隣接リストを作る必要がない

・応用が出来るかもしれない (動的な判定とかでダイコネと組み合わせられそう)

実装例

コドフェス2017qualB-C 3stepsの実装を載せます (実際はこの上にUnionFindTreeの実装が入ってます)

Submission #3016274 - CODE FESTIVAL 2017 qual B

#include<iostream>
#include<cstdint>
#include<vector>
template<class T>
using vec_alias = ::std::vector<T>;
 
int main() {
    using u32 = ::std::uint_fast32_t;
    using u64 = ::std::uint_fast64_t;
    u32 n, m;
    ::std::cin >> n >> m;
    union_find<vec_alias> uf(n * 2);
 
    for (u32 i = 0;i < m;++i) {
        u32 a, b;
        ::std::cin >> a >> b;
        --a;
        --b;
        uf.unite(a, b + n);
        uf.unite(a + n, b);
    }
 
    if (uf.same(0, n)) {
        ::std::cout << static_cast<u64>(n)*(n - 1) / 2 - m << ::std::endl;
        return 0;
    }
 
    u64 cnt = 0;
    for (u32 i = 0;i < n;++i)
        if (uf.same(0, i))
            ++cnt;
 
    ::std::cout << (static_cast<u64>(n) - cnt) * cnt - m << ::std::endl;
 
    return 0;
}