Submission #2522505

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)

struct UnionFind {
  vector<int> v;
  UnionFind(int n): v(n) {
    rep(i, n) v[i] = i;
  }
  int find(int x) {
    if(v[x] == x) return x;
    return v[x] = find(v[x]);
  }
  void unite(int x, int y) {
    v[find(x)] = find(y);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> p(n);
  rep(i, n) cin >> p[i];
  vector<int> x(m), y(m);
  rep(i, m) cin >> x[i] >> y[i];

  UnionFind uf(n);
  rep(i, m) uf.unite(x[i]-1, y[i]-1);

  int cnt = 0;
  rep(i, n) cnt += uf.same(p[i]-1, i);
  cout << cnt << endl;

  return 0;
}

Submission Info

Judge Result