Submission #2499950

---

Source Code Expand

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

#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))

typedef long long LL;

int uf[100000];
set<int> K[100000];
set<int> P[100000];

int Find(int num){
  if(uf[num]==num){
    return num;
  }else{
    uf[num]=Find(uf[num]);
    return uf[num];
  }
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> p(n);
  for(int i=0;i<n;i++){
    cin >> p[i];
    p[i]--;
  }
  for(int i=0;i<n;i++){
    uf[i]=i;
  }
  int x,y;
  for(int i=0;i<m;i++){
    cin >> x >> y;
    x--;
    y--;
    x=Find(x);
    y=Find(y);
    uf[x]=y;
  }
  for(int i=n;i>=0;i--){
    Find(i);
  }
  for(int i=0;i<n;i++){
    K[uf[i]].insert(i);
    P[uf[i]].insert(p[i]);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    for(set<int>::iterator itr=K[i].begin();itr!=K[i].end();itr++){
      if(P[i].find((*itr))!=P[i].end()){
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result