2部グラフ判定

競技プログラミング

アニマエールのOP・EDを聞いたら、見返す機運が高まってるえぬわいです。

今日は、蟻本に載ってる2部グラフ判定を自分で実装して理解しました。

ポイントとしては、

  • とりあえず、塗っていって判定する
  • 塗ってる最中でダメだと思ったら打ち切る
  • 色は、符号を反転させたもので区別するとコードが減らせる

と言ったところかな。

pythonで書いたらこんな感じ

from collections import defaultdict

G = defaultdict(list)
# 色を保持するリスト。0 で初期化しておいて、訪れたことがあるかにも使う
# 1, -1 のように反転させた符号にしておけば、-をつけただけでよくなる
C = []

N, E = map(int, input().split())
for i in range(N):
    C.append(0)
for i in range(E):
    fr, to = map(int, input().split())
    G[fr].append(to)
    G[to].append(fr)

def rec(pos, color):
    global C
    C[pos] = color
    for to in G[pos]:
        if C[to] == color:
            return False
        elif C[to] == 0 and not rec(to, -color):
            return False
    return True

ans = True
for i in range(N):
    if C[i] == 0:
        ans &= rec(i, 1)
print(ans)

計算量は、辺と頂点を 1 度ずつ見ているので、O(|E|+|V|)となるらしい。ふむ。俺もふわふわのクッションが足りないのかもしれない。ふむ。