Submission #8398336

---

Source Code Expand

#include<bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ll long long

using namespace std;

struct UnionFind {
  vector<int> par, rank;

  UnionFind(int n){
    par.resize(n+1);
    fill(par.begin(), par.end(), -1);
    rank.resize(n+1);
  }

  int root(int x){
    if(par[x] < 0){
      return x;
    }

    par[x] = root(par[x]);

    return par[x];
  }

  void unite(int x, int y){
    int rx=root(x);
    int ry=root(y);

    if(rx!=ry){
      if(rank[rx] >= rank[ry]){
        par[ry]=rx;

        if(rank[rx]==rank[ry]){
          rank[rx] += 1;          
        }
      }else{
        par[rx] = ry;
      }
    }
  }

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

int main(){
  int n, m;
  cin>>n>>m;
  vector<int> p;
  rep(i, n){
    int t;
    cin>>t;
    p.push_back(t);
  }
  UnionFind uf(n);

  rep(i, m){
    int x,y;
    cin>>x>>y;
    
    uf.unite(x,y);
  }
  
  int result=0;
  rep(i, n){
    if(uf.same(p[i], i+1))result++;
  }
  
  cout<<result;
  
  return 0;
}

Submission Info

Judge Result