ARC041 D - 辺彩色
https://atcoder.jp/contests/arc041/tasks/arc041_d
解答
code: python
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)
n, m = map(int, input().split())
abc = list(input().split()) for _ in range(m)
d = defaultdict(list)
# 辺の正しい色: colori == 1 -> 'r', 0 -> 'b'
color = -1 for _ in range(m)
tar = [0 for _ in range(n) for _ in range(n)]
visited = False for _ in range(m)
dis = 0 for _ in range(n)
for idx, (a, b, c) in enumerate(abc):
a, b = int(a) - 1, int(b) - 1
da.append(b)
db.append(a)
tarab = idx
tarba = idx
coloridx = 1 if c == 'r' else 0
def dfs(now, c, l, visited, dis):
if disnow < 0:
disnow = l
# すでに訪れたことがある、つまり、閉路であり、その長さが奇数だったら
elif abs(l - disnow) % 2:
print('Yes')
exit()
for next in dnow:
# 辺の番号の取得
num = tarnownext
if visitednum:
continue
# 正しい辺の色と塗る色が同じだった場合のみ、続ける
if colornum == c:
visitednum = True
dfs(next, c^1, l+1, visited, dis)
# 始点と色で全探索
for i in range(n):
for c in range(2):
# visited の初期化
for k in range(m):
visitedk = False
# dis はすべて負にしておく
for k in range(n):
disk = -1
# 始点 i, 色 c, 長さ 0 でスタート
dfs(i, c, 0, visited, dis)
# 全て塗ることができる
if all(visited):
print('Yes')
exit()
print('No')
テーマ
#graph
蟻本 2-5 二部グラフ判定
メモ
ARC 041 D 辺彩色(2)
https://img.atcoder.jp/arc041/editorial.pdf
提出
WA
code: python
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
abc = list(input().split()) for _ in range(m)
d = defaultdict(list)
for a, b, c in abc:
a, b = int(a), int(b)
da.append(b)
db.append(a)
# print(d)
# defaultdict(<class 'list'>, {1: 2, 2: 1, 3, 3: 2, 4, 4: 3, 5, 5: 4, 6, 6: 5})
color = 0 for _ in range(n+1)
def dfs(i, c):
colori = c
for v in di:
if colorv == c:
return False
elif colorv == 0 and not dfs(v, -c):
return False
return True
print("Yes") if dfs(1,1) else print("No")