Maximum-Cup 2018 C 嘘つきな天使たち
最近努力が足りていないえぬわいです。
続きです。
2 部グラフで解けた。塗った時の数を記録していけば、おk。連結であることが保証されていないので、その点は気をつけた。自分で考えてACできるとちょーきもちー。
from collections import defaultdict G = defaultdict(list) N = int(input()) for i in range(N): to = int(input()) G[i].append(to-1) G[to-1].append(i) C = [0 for i in range(N)] tmp = dict() tmp[1] = 0; tmp[-1] = 0 def rec(pos, color): global C C[pos] = color tmp[color] += 1 ans = True for to in G[pos]: if color == C[to]: return False elif C[to] == 0: ans &= rec(to, -color) return ans ans = 0 for i in range(N): tmp[1] = 0; tmp[-1] = 0 if C[i] == 0: if not rec(i, 1): print('-1') break ans += max(tmp[1], tmp[-1]) else: print(ans)
再帰の回数の設定忘れてたけど通った。