ARC041 D - 辺彩色
解答
code: python
from collections import defaultdict
import sys
sys.setrecursionlimit(100000000)
n, m = map(int, input().split())
d = defaultdict(list)
# 辺の正しい色: colori == 1 -> 'r', 0 -> 'b' for idx, (a, b, c) in enumerate(abc):
a, b = int(a) - 1, int(b) - 1
coloridx = 1 if c == 'r' else 0 def dfs(now, c, l, visited, dis):
# すでに訪れたことがある、つまり、閉路であり、その長さが奇数だったら
elif abs(l - disnow) % 2: print('Yes')
exit()
# 辺の番号の取得
continue
# 正しい辺の色と塗る色が同じだった場合のみ、続ける
dfs(next, c^1, l+1, visited, dis)
# 始点と色で全探索
for i in range(n):
for c in range(2):
# visited の初期化
for k in range(m):
# dis はすべて負にしておく
for k in range(n):
# 始点 i, 色 c, 長さ 0 でスタート
dfs(i, c, 0, visited, dis)
# 全て塗ることができる
if all(visited):
print('Yes')
exit()
print('No')
テーマ
メモ
提出
WA
code: python
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
d = defaultdict(list)
for a, b, c in abc:
a, b = int(a), int(b)
# print(d)
# defaultdict(<class 'list'>, {1: 2, 2: 1, 3, 3: 2, 4, 4: 3, 5, 5: 4, 6, 6: 5}) def dfs(i, c):
return False
elif colorv == 0 and not dfs(v, -c): return False
return True
print("Yes") if dfs(1,1) else print("No")