ARC 041 D 辺彩色(1)
続きをやっている。
普通にわかんなかったが?(半ギレ)
解答見る。
考察で、逆順に辿ると、上書きする機能がなくなる←天才か?
始点と最初の色で全探索。それプラス、奇数サイクルのことを考えるものらしい。
辺彩色のコードわからんとなってそれっぽいものを書いた。とりあえず、奇数サイクルを考えないもの。当然WAだが。初歩として。明日は、ACする。
import sys sys.setrecursionlimit(100000) from collections import defaultdict N, M = map(int, input().split()) G = defaultdict(list) C = [[0 for i in range(N)] for j in range(N)] T = [[0 for i in range(N)] for j in range(N)] E = [] for i in range(M): t, f, c = input().split() t = int(t) - 1 f = int(f) - 1 G[t].append(f); G[f].append(t) if c == 'r': T[f][t] = 1 T[t][f] = 1 else: T[f][t] = -1 T[t][f] = -1 E.append([t, f]) def rec(pos, c): global C ret = True for to in G[pos]: if C[pos][to] == 0: C[pos][to] = c C[to][pos] = c if C[pos][to] != T[pos][to]: return False ret &= rec(to, -c) return ret # 逆に辿っていく ans = False for i in range(N): for j in [1, -1]: for t, f in E: C[t][f] = 0 C[f][t] = 0 ans |= rec(i, j) print('Yes' if ans else 'No')