二部グラフ判定

隣り合う頂点が違う色になるように、BFS で頂点を $0$ と $1$ に塗っていきます。非連結なグラフでも使え、再帰は使いません。

• bipartite(g): 無向グラフの隣接リスト g[v] = [to, ...] が二部グラフなら各頂点の色（ $0$ か $1$）のリストを、そうでなければ None を返す。 $O(N + M)$

各連結成分の色は、成分ごとに $0$ と $1$ を入れ替えても条件を満たします。

コード

def bipartite(g):
    # 二部グラフなら各頂点の色（0 か 1）のリスト、そうでなければ None
    n = len(g)
    color = [-1] * n
    for s in range(n):
        if color[s] != -1:
            continue
        color[s] = 0
        q = [s]
        for v in q:
            for to in g[v]:
                if color[to] == -1:
                    color[to] = color[v] ^ 1
                    q.append(to)
                elif color[to] == color[v]:
                    return None
    return color