Submission #8424271

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

static const int MAX = 1e5 + 1;

// Union-Find木
int par[MAX]; // 親の番号

// n要素で初期化
void init(int n) {
  for(int i = 0; i < n; i++) par[i] = i;
}

// 木の根を求める
int find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyが同じ集合に属するか
bool same(int x, int y) {
  return find(x) == find(y);
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return;
  par[x] = y;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, m;
  cin >> n >> m;
  
  vector<int> p(n);
  for(int i = 0; i < n; i++) cin >> p.at(i);
  
  init(n);
  
  int x, y;
  for(int i = 0; i < m; i++){
    cin >> x >> y;
    unite(x, y);
  }
  
  int ans = 0;
  for(int i = 0; i < n; i++){
    if(same(i + 1, p.at(i))) ans++;
  }
  
  cout << ans << "\n";
}

Submission Info

Judge Result