Pythonで理解する蟻本「2-5 二部グラフ判定」(p.93) - クルトンのプログラミング教室

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-5 二部グラフ判定」(p.93)
のコードをPythonで書き直したものとなっています。

入力
入力例
- 入力例1
- 入力例1
解答

入力

蟻本の入力例ではグラフが書かれていただけだったので、この記事ではAtCoderでよくあるような入力形式で入力例を書き直しておきました。

そのため、グラフの入力を受け取る部分は蟻本に載っているコードとは異なります。

この入力の受け取り方は『Pythonで理解する蟻本「2-5 隣接リスト」(p.91)』に載っているのでそちらを参考にしてください。

$n:頂点数\\m:辺数\\2点s_i,\,t_iの間に無向辺が存在する(1\leq{i}\leq{m})$

$n\\m\\s_1\,t_1\\:\\s_m\,t_m$

入力例

入力例1

3
3
0 1
0 2
1 2

入力例1

4
4
0 1
0 3
1 2
2 3

解答

# DFSを使うため再帰限界に引っかからないようにしておく
import sys
sys.setrecursionlimit(4100000)

MAX_V = 1000

# 入力
V = int(input())    # 頂点数
E = int(input())    # 辺数
G = [[] for _ in range(MAX_V)]    # グラフ
for i in range(E):
    # sからtへの辺を張る
    s, t = map(int,input().split())
    G[s].append(t)
    G[t].append(s)

color = [0] * MAX_V    # 頂点iの色(1 or -1)

# 頂点を1と-1で塗っていく
def dfs(v, c):
    color[v] = c    # 頂点vをcで塗る
    for i in range(len(G[v])):
        # 隣接している頂点が同じ色ならFalse
        if color[G[v][i]] == c:
            return False
        # 隣接している頂点がまだ塗られていないなら-cで塗る
        if color[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False
    # すべての頂点を塗れたらTrue
    return True

for i in range(V):
    if color[i] == 0:
        # まだ頂点iが塗られていなければ1で塗る
        if not dfs(i, 1):
            print("No")
            sys.exit()
print("Yes")