Union-Find

問題

各親に属する全ての子のfを1にする

f[i(全ての子)] = i(1) にできるなら ans++

struct UnionFind {vector<int> par; // uf(x,y)->y
    UnionFind(int NV) //宣言
    { par.clear(); rep(i, 0, NV) par.push_back(i); } //値の代入
    void reset() 
    { rep(i, 0, par.size()) par[i] = i; } //自身を親とする
    int operator[](int x) 
    { return par[x] == x ? x : par[x] = operator[](par[x]); } //自身が親か？
    void operator()(int x, int y) 
    {x = operator[](x); y = operator[](y);if (x != y) par[x] = y;}}; //同じ木か？

int N, M, P[101010]; 
vector<int> idx[101010]; //idx[親] = 子
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) {
        //j(親iである子全て)
        fore(j, idx[i]) f[j] = 1; //セット
        fore(j, idx[i]) if (f[P[j]]) ans++; //P[j](j番目の整数) 
        fore(j, idx[i]) f[j] = 0; //リセット
    }
    cout << ans << endl;
}