Submission #4016269

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;


#define MAX_N 100000
int par[MAX_N];
int myrank[MAX_N];

void init(int n){
    for(int i = 0; i < n; i++){
        par[i] = i;
        myrank[i] = 0;
    }
}

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

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

    if(myrank[x] < myrank[y]){
        par[x] = y;
    }
    else{
        par[y] = x;
        if(myrank[x] == myrank[y])  myrank[x]++;
    }
}

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

int main(){
    int N, M;
    int p[110000];
    int x[110000], y[110000], ind[110000];
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> p[i];
        ind[p[i]] = i+1;
    }
    for(int i = 0; i < M; i++){
        cin >> x[i] >> y[i];
    }
    init(N+1);
    for(int i = 0; i < M; i++){
        unite(x[i], y[i]);
    }
    int res = 0;
    for(int i = 1; i <= N; i++){
        if(same(i, ind[i])){
            res++;
        }
    }

    cout << res << endl;

    return 0;

}

Submission Info

Judge Result