Submission #8445116

---

Source Code Expand

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

#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) (x).begin(), (x).end()

struct UF {
  int n;
  vector< int > par;
  UF(int n) : n(n), par(n, -1) {}
  int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
  int size(int x) { return -par[find(x)]; }
  bool same(int a, int b) { return find(a) == find(b); }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b) return;
    if(par[a] < par[b]) swap(a, b);
    par[b] += par[a];
    par[a] = b;
  }
  void clear() { par.assign(n, -1); }
};

using P = pair<int, int>;

inline void Main() {
  // code
  int N, M, x, y, res = 0;
  map<int, int> MII;
  cin >> N >> M;
  rep(i, N) {
    cin >> x;
    MII.insert(P(x-1, i));
  }
  UF uf(N);
  rep(i, M) {
    cin >> x >> y;
    uf.unite(x-1, y-1);
  }

  rep(i, N) {
    int t = N - 1 - i;
    if (uf.same(t, MII.at(t))) {
      res++;
    }
  }

  cout << res << endl;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}

Submission Info

Judge Result