ARC 041 D 辺彩色(1)

qiita.com

続きをやっている。

atcoder.jp

普通にわかんなかったが?(半ギレ)

解答見る。

考察で、逆順に辿ると、上書きする機能がなくなる←天才か?

始点と最初の色で全探索。それプラス、奇数サイクルのことを考えるものらしい。

辺彩色のコードわからんとなってそれっぽいものを書いた。とりあえず、奇数サイクルを考えないもの。当然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')