Maximum-Cup 2018 C 嘘つきな天使たち

最近努力が足りていないえぬわいです。

qiita.com

続きです。

atcoder.jp

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)

再帰の回数の設定忘れてたけど通った。