Submission #8402116

---

Source Code Expand

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
using namespace std;

typedef long long ll;
int p[100005];
int q[100005];
struct UnionFind{
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
    UnionFind(int n): par(n), rank(n), sizes(n){
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
            sizes[i] = 1;
        }
    }

    int root(int x){
        if(par[x] == x)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        else {
            if(rank[x] < rank[y]){
                par[x] = y;
                sizes[y] += sizes[x];
            } else {
                par[y] = x;
                sizes[x] += sizes[y];
                if(rank[x] == rank[y]) rank[x]++;
            }
        }
    }

    int size(int x){
        return sizes[root(x)];
    }
};

int main(){
   int N, M;
   cin >> N >>M;
   for(int i = 1; i <= N; i++){
      cin >> p[i];
      q[p[i]] = i;
   }
   UnionFind uni(N+1);
   for(int i = 1; i <= M; i++){
      int x, y;
      cin >> x >> y;
      uni.unite(x, y);
   }
   int ans = 0;
   for(int i = 1; i <= N; i++){
      if(uni.root(i) == uni.root(q[i]))
         ans++;
   }
   cout << ans << endl;
}

Submission Info

Judge Result