蟻本 2-5 二部グラフ判定 - 競プロ

蟻本 2-5 二部グラフ判定

code: python

# 入力のつもり。esはよくある隣接リストで辺を表したもの。

N = 5

es = 1,3],0,2,1,3,0,2,4,[3 # True

#es = 1,2,3],0,2,0,1,0,4,[3 # False

# n個の頂点の色を初期化。0:未着色、1:黒、-1:白

colors = 0 for i in range(N)

# 頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse

def dfs(v,color):

# 今いる点を着色

colorsv = color

#今の頂点から行けるところをチェック

for to in esv:

#同じ色が隣接してしまったらFalse

if colorsto == color:

return False

#未着色の頂点があったら反転した色を指定し、再帰的に調べる

if colorsto == 0 and not dfs(to, -color):

return False

# 調べ終わったら矛盾がないのでTrue

return True

# 2部グラフならTrue, そうでなければFalse

def is_bipartite():

return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

print(is_bipartite())

テーマ