Equals [AtCoder Regular Contest 097 D]

https://beta.atcoder.jp/contests/arc097/tasks/arc097_b

前提知識

• UnionFind

解法

https://beta.atcoder.jp/contests/arc097/submissions/2495934

aとbがスワップ可能、かつ、bとcがスワップ可能であれば、aとcはスワップ可能である。
よって、スワップ可能なペアをたどっていける場合は好きな順番にできるということである。
もう少し数学的に言い換えると、1～Nの整数を頂点、M個のペアを辺として無向グラフを作る。
すると、この連結成分内であれば頂点に割り当てられた数はどんな順番にもできるということである。
　
なのでUnionFindを使って連結成分に分けよう。
連結成分毎にpi=iと出来る個数を数えていく。
そのために配列fを使っている。
fore(j, idx[i]) f[j] = 1; // 連結成分の添字に1を入れる
fore(j, idx[i]) if (f[P[j]]) ans++;
// 連結成分の添字が指す順列の数を使ってfを見る。
// 1があれば対応する添字があるのでans++
fore(j, idx[i]) f[j] = 0; // 連結成分の添字に0を入れる（クリアしておく）

int N, M, P[101010];
vector<int> idx[101010];
int f[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) {
        cin >> P[i];
        P[i]--;
    }
 
    UnionFind uf(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        uf(a, b);
    }
 
    rep(i, 0, N) idx[uf[i]].push_back(i);
 
    int ans = 0;
    rep(i, 0, N) {
        fore(j, idx[i]) f[j] = 1;
        fore(j, idx[i]) if (f[P[j]]) ans++;
        fore(j, idx[i]) f[j] = 0;
    }
    cout << ans << endl;
}