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

https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_c

前提知識

• N頂点N辺のグラフ

解法

https://beta.atcoder.jp/contests/maximum-cup-2018/submissions/2312774

まず、「N頂点N辺」「全ての頂点の入次数が1」である有向グラフは、全ての連結成分がサイクルとなる有向グラフとなる。
こういう問題への取り組みの1つとして連結成分毎に考えるというのがあるので、まずはその方面で考えてみる。
サイクルなので、1つを天使と決めると他を全て決めることができる。
自分に戻ってきたときにちゃんと天使である必要があるが、このためにはサイクルの長さが偶数である必要がある。
よって、連結成分でサイクルの長さが奇数の物があれば「-1」である。
サイクルの長さが偶数であれば、その半分が悪魔となるはずなので、サイクルの長さの半分を悪魔としてカウントする。
UnionFindを使って連結成分でまとめたあと、サイクルの長さが偶数なら、半分の総和を取っていくと答えになる。

int N, A[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
int solve() {
    UnionFind uf(N);
    rep(i, 0, N) cnt[i] = 1;
 
    rep(i, 0, N) {
        int j = A[i];
        if (uf[i] != uf[j]) {
            int sm = cnt[uf[i]] + cnt[uf[j]];
            uf(i, j);
            cnt[uf[i]] = sm;
        }
    }
 
    int ans = 0;
    rep(i, 0, N) if (uf[i] == i) {
        if (cnt[i] % 2 == 1) return -1;
        ans += cnt[i] / 2;
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) A[i]--;
    cout << solve() << endl;
}