二部グラフ判定

参考

アルゴリズムの概要

参考に書いてあるとおりにやる.

すなわち, 頂点 \(u\) がグループ \(1,2\) にあることを表す述語 \(P^1(u), P^2(u)\) を用意して, エッジ \(e = (u, v)\)\((P^1(u) \land P^2(v)) \lor (P^2(u) \land P^1(v))\) と解釈して論理グラフを組み立てて(頂点が命題で連結なときには同時に成り立つ), 最後に矛盾が無いことを確認する.

実装

論理グラフは同じグラフに所属するかだけが問題なので, これを UnionFind で実装する.

fn is_bipartite_graph(n: usize, g: &Vec<Vec<usize>>) -> bool {
    let mut uf = UnionFind::new(n * 2);
    for i in 0..n {
        for &j in g[i].iter() {
            if i >= j { continue }
            uf.merge(2 * i, 2 * j + 1);
            uf.merge(2 * i + 1, 2 * j);
        }
    }
    for i in 0..n {
        if uf.is_same(2 * i, 2 * i + 1) { return false }
    }
    true
}