D - Equals | AtCoder Regular Contest 097

(x[j], y[j])を辺とするようなグラフを考える。このグラフの各連結成分内では要素は各辺を介したスワップによって自由に配置できる。よって頂点iを含む連結成分にp[i]が含まれるかを調べればいい。連結成分の識別にはUnion Find木を使うと便利。

int N, M;
vi P(N);
rep(i, N) {
    cin >> P[i];
    --P[i];
}
UnionFind uf(N);
vi X(M), Y(M);
rep(i, M) {
    cin >> X[i] >> Y[i];
    --X[i];
    --Y[i];
    uf.unite(X[i], Y[i]);
}
int re = 0;
rep(i, N) if (uf[i] == uf[P[i]]) re++;
cout << re << endl;