算法

(并查集) $O(n)$

本题实际上是图论问题，对于每一个交换可以把两点连一条边，然后可以看到有若干连通块，对于同一连通块里的数可以交换位置，于是我们可以想到并查集，对于每个点如果它和自身的父节点在同一连通块的话，那么说明这点可以做到 $p_i = i$。

类题：

数字移动

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main() {
    int n, m;
    cin >> n >> m;

    vector<int> p(n);
    rep(i, n) cin >> p[i];

    UnionFind tree(n);

    rep(mi, m) {
        int x, y;
        cin >> x >> y;
        tree.unite(x - 1, y - 1);
    }

    int ans = 0;
    rep(i, n) if (tree.same(i, p[i] - 1)) ++ans;

    cout << ans << '\n';

    return 0;
}