Problem:
 Score : 400 points    Problem Statement We have a permutation of the integers from 1 through N , p_1 , p_2 , .., p_N .
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1) , (x_2,y_2) , .., (x_M,y_M) .
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i ( 1  ≤  i  ≤  N ) such that p_i = i is maximized:   Choose j such that 1  ≤  j  ≤  M , and swap p_{x_j} and p_{y_j} .   Find the maximum possible number of i such that p_i = i after operations.      Constraints  2  ≤  N  ≤  10^5  1  ≤  M  ≤  10^5  p is a permutation of integers from 1 through N .  1  ≤  x_j,y_j  ≤  N  x_j  ≠  y_j  If i  ≠  j , \{x_i,y_i\}  ≠  \{x_j,y_j\} .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  p_1  p_2  ..  p_N  x_1  y_1  x_2  y_2  :  x_M  y_M       Output Print the maximum possible number of i such that p_i = i after operations.        Sample Input 1 5 2
5 3 1 4 2
1 3
5 4      Sample Output 1 2  If we perform the operation by choosing j=1 , p becomes 1 3 5 4 2 , which is optimal, so the answer is 2 .       Sample Input 2 3 2
3 2 1
1 2
2 3      Sample Output 2 3  If we perform the operation by, for example, choosing j=1 , j=2 , j=1 in this order, p becomes 1 2 3 , which is obviously optimal.
Note that we may choose the same j any number of times.       Sample Input 3 10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9      Sample Output 3 8       Sample Input 4 5 1
1 2 3 4 5
1 5      Sample Output 4 5  We do not have to perform the operation.

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007

class UnionFind:
    def __init__(self, n):
        
        
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

    def root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.root(self.table[x])
            return self.table[x]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1


n, m = LI()
P = LI()
uf = UnionFind(n)
for _ in range(m):
    x, y = LI()
    uf.union(x - 1, y - 1)



print(sum([bool(uf.is_same(P[i] - 1, i)) for i in range(n)]))

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N+1)
for i in range(M):
    a, b = map(int,input().split())
    uf.union(a,b)
ans = 0
for i in range(1,N+1):
    if uf.same(i,P[i-1]):
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        uf.union(x-1, y-1)
    ans = 0
    for i in range(N):
        if uf.same(P[i]-1, i):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from __future__ import print_function


import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )



import random

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):       
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    
def main():
    n_len_of_seq, m_num_of_pairs = map(int, input().split())
    union_find_forest = UnionFind(n_len_of_seq) 
    p_seq  = list(map(int, input().split()))
    p_seq = [p_seq[i] - 1 for i in range(len(p_seq))]

    
    
    

    for index in range(m_num_of_pairs): 
        x_pair,y_pair = map(int, input().split())
        x_pair-=1
        y_pair-=1
        union_find_forest.union( x_pair , y_pair) 
        
        
        
    cnt=0
    for i in range(n_len_of_seq): 
        if union_find_forest.same(i, p_seq[i]): 
            
            cnt+=1
    
    print(cnt)
    
    
    
    
    
    
    
    
    

    
    return

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n

    def find(self,x):
        if self.PAR[x] == x:
            return x
        else:
            self.PAR[x] = self.find(self.PAR[x])
            return self.PAR[x] 

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.RANK[x] < self.RANK[y]:
            self.PAR[x] = y
        else:
            self.PAR[y] = x
            if self.RANK[x] == self.RANK[y]:
                self.RANK[x] += 1

    def same(self,x,y):
        return self.find(x) == self.find(y)

N,M = map(int,input().split())
Data = list(map(int,input().split()))
graph = UnionFind(N+1)
for _ in range(M):
    x1,y1 = map(int,input().split())
    graph.union(x1,y1)

ans = 0
for i in range(1,N+1):
    if graph.same(i,Data[i-1]):
        ans+=1

print(ans)

Solution (Python):
N, M = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


d = DisjointSet(N)
for i in range(M):
    xi, yi = map(int, input().split())
    d.unite(p[xi - 1], p[yi - 1])

ans = 0
for i in range(N):
    if d.find(p[i]) == d.find(i):
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)

N, M = map(int, input().split())
P = [-1 for i in range(N)]
A = [int(a)-1 for a in input().split()]
for _ in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)

X = [[] for _ in range(N)]
Y = [[] for _ in range(N)]
for i in range(N):
    X[par(i)].append(i)
    Y[par(i)].append(A[i])

ans = 0
for i in range(N):
    ans += len(set(X[i]) & set(Y[i]))

print(ans)

Solution (Python):


import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))
xy = sys.stdin.readlines()

neighbor = [[] for _ in range(N)]
for idx in range(M):
    x,y = map(int, xy[idx].split())
    neighbor[x-1].append(y-1)
    neighbor[y-1].append(x-1)
    
can_swap = []
visited = [-1]*N

for start in range(N):
    if visited[start] == -1:
        tmp = [start] 
        d = deque([start])
        while d:
            current_point = d.pop()
            visited[current_point] = 1
            for next_point in neighbor[current_point]:
                if visited[next_point] == -1:
                    d.append(next_point)
                    tmp.append(next_point)
        can_swap.append(tmp)                

ans = 0
for idx_group in can_swap:
    tmp_p = [p[idx]-1 for idx in idx_group]
    ans += len(set(tmp_p) & set(idx_group))

print(ans)

Solution (Python):


N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]


root = [-1] * N 


rank = [1] * N


def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find_root(root[x])
        return root[x]
    

def union(x,y):
    
    root_x = find_root(x)
    root_y = find_root(y)
    if root_x == root_y:
        return
    elif rank[root_x] > rank[root_y]: 
        root[root_x] += root[root_y] 
        root[root_y] = root_x 
    else:
        root[root_y] += root[root_x]
        root[root_x] = root_y
        
        if rank[root_x] == rank[root_y]:
            rank[root_y] += 1 
            
for idx in range(M):
    union(xy[idx][0]-1, xy[idx][1]-1)
    
ans = 0
for i in range(N):
    if find_root(i) == find_root(p[i]-1):
        ans += 1
        
print(ans)

Solution (Python):


from collections import deque

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

neighbor = [[] for _ in range(N)]
for idx in range(M):
    neighbor[xy[idx][0]-1].append(xy[idx][1]-1)
    neighbor[xy[idx][1]-1].append(xy[idx][0]-1)
    
can_swap = []
visited = [-1]*N

for start in range(N):
    if visited[start] == -1:
        tmp = [start] 
        d = deque([start])
        while d:
            current_point = d.pop()
            visited[current_point] = 1
            for next_point in neighbor[current_point]:
                if visited[next_point] == -1:
                    d.append(next_point)
                    tmp.append(next_point)
        can_swap.append(tmp)                

ans = 0
for idx_group in can_swap:
    tmp_p = [p[idx]-1 for idx in idx_group]
    ans += len(set(tmp_p) & set(idx_group))

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int,input().split())
P = list(map(int,input().split()))
XY = [list(map(int,input().split())) for _ in range(M)]
pos = [0] * (N + 1)
for i in range(N):
  pos[P[i]] = i

uf = UnionFind(N)
for i in range(M):
  uf.union(XY[i][0]-1,XY[i][1]-1)

ans = 0
for i in range(N):
  if uf.same(i,pos[i+1]):
    ans += 1
print(ans)

Solution (Python):
import sys
from operator import itemgetter
from itertools import groupby
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
p = list(map(int, readline().split()))
xy = map(int, read().split())


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if x == y:
            return
        
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


tree = UnionFind(N)
for x, y in zip(xy, xy):
    tree.Unite(x, y)

group = tree.root[1:]
number = list(range(1, N + 1))
answer = 0

for i in range(N):
    if tree.isSameGroup(number[i], p[i]):
        answer += 1

print(answer)

Solution (Python):
import sys



class AlgUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    p = list(map(int, input().rstrip('\n').split()))
    uf = AlgUnionFind(n)
    for i in range(m):
        x, y = list(map(int, input().rstrip('\n').split()))
        uf.union(x-1, y-1)
    for i in range(n):
        p[i] = [p[i]-1, p[i]-1 == i]
    while True:
        c_sw = False
        for i in range(len(p)):
            tn = p[i][0]
            if not p[i][1] and not p[tn][1]:
                if uf.same(tn, p[tn][0]):
                    p[tn][0], p[i][0] = p[i][0], p[tn][0]
                    p[i][1] = p[i][0] == i
                    p[tn][1] = p[tn][0] == tn
                    c_sw = True
        if not c_sw:
            break
    cnt = 0
    for i in range(n):
        cnt += p[i][1]
    print(cnt)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
class UnionFind:
  def __init__(self,nodes):
    self.parents={node: node for node in nodes}
  def root(self,x):
    if x==self.parents[x]:
      return x
    else:
      rt=self.root(self.parents[x])
      self.parents[x]=rt
      return rt
  def find(self,x,y):
    return self.root(x)==self.root(y)
  def union(self,x,y):
    self.parents[self.root(x)]=self.root(y)

n,m=map(int,input().split())
P=list(map(int,input().split()))
uf=UnionFind(range(1,n+1))
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x,y)
  
ans=0
for i in range(1,n+1):
  if uf.find(i,P[i-1]):
    ans+=1
print(ans)

Solution (Python):
from collections import defaultdict
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

ans = 0
for n in range(1,N+1):
    if uf.find(n,p[n-1]):
        ans += 1
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

inf=float("inf")
n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

uf=WeightedUnionFind(n+1)
cnt=0
for i in range(m):
    uf.union(xy[i][0],xy[i][1],0)
for i in range(n):
    if uf.same(i+1,p[i]):
        cnt+=1
print(cnt)

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
xs=[tuple(map(int,input().split())) for _ in range(m)]
def root(n):
  if union[n]==n:
    return n
  union[n]=root(union[n])
  return union[n]
union={x:x for x in range(1,n+1)}
for x,y in xs:
  union[root(x)]=root(y) 
print(sum(root(i+1)==root(p[i]) for i in range(n)))

Solution (Python):
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n,q=map(int,input().split())
size=[1]*n
ans=0 
l=[int(i) for i in input().split()]
parent=[i for i in range(n)]
for i in range(q):
    a,b=map(int,input().split())
    parent,size=union(parent,size,a-1,b-1)
for i in range(n):
    if find(parent,i)==find(parent,l[i]-1):
        ans+=1 
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m=map(int,input().split())
    p = list(map(int,input().split()))
    uf = UnionFind(n)
    res = 0
    for _ in range(m):
        x,y=map(int,input().split())
        uf.union(x-1,y-1)
    for i in range(n):
        if uf.same(p[i]-1,i):
            res += 1
    print(res)

main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m=map(int,input().split())
    p = list(map(int,input().split()))
    uf = UnionFind(n)
    res = 0
    for _ in range(m):
        x,y=map(int,input().split())
        uf.union(x-1,y-1)
    for i in range(n):
        if uf.same(p[i]-1,i):
            res += 1
    print(res)

main()

Solution (Python):
from collections import deque

N,M=map(int,input().split())
p=list(map(int,input().split()))

out=[set() for i in range(N+1)]

for k in range(M):
    x,y=map(int,input().split())
    out[x].add(y)
    out[y].add(x)

rch=[False for i in range(N+1)]
ans=0
q=deque()
for i in range(1,N+1):
    if not rch[i]:
        si=set()            
        q.append(i)
        rch[i]=True
        si.add(i)
        while q:
            u=q.popleft()
            for v in out[u]:
                if not rch[v]:
                    q.append(v)
                    rch[v]=True
                    si.add(v)
        sv={p[i-1] for i in si}
        ans+=len(si&sv)
              
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (n+1)

    def find(self, x):
        """ 根の検索(グループ番号と言えなくもない) """
        
        if self.par[x] == x:
            return x
        else:
            
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """ 併合 """
        
        x = self.find(x)
        y = self.find(y)

        
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """ あるノードの属する集合のノード数 """
        return self.size[self.find(x)]
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1

N, M = MAP()
P = [p-1 for p in LIST()]

uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    uf.union(P[a], P[b])

cnt = 0
for i in range(N):
    p = P[i]
    if uf.same(p, i):
        cnt += 1
print(cnt)

Solution (Python):

n,m=map(int,input().split())
p=list(map(int,input().split()))
p=[0]+p
data=[[] for _ in range(n+1)]
flag=[0]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    data[x].append(y)
    data[y].append(x)
tree=[0]*(n+1)
for i in range(1,n+1):
    if flag[i]==0:
        que=[i]
    while que:
        h=que.pop()
        flag[h]=1
        tree[h]=i
        for u in data[h]:
            if flag[u]==0:
                que.append(u)
count=0
for i in range(1,n+1):
    if tree[i]==tree[p[i]]:
        count+=1
print(count)

Solution (Python):
class UnionFind:
    def __init__(self, data):
        self.parent = {}
        self.rank = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.rank[i] = 0
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.find(x) == self.find(y):
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            return
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]: self.rank[y] += 1
            return

N, M = map(int, input().split())
P = list(map(int, input().split()))
L = []
for i in range(M):
    L.append([int(x) for x in input().split()])
tree = UnionFind(N)
for i in range(M):
    tree.unite(P[L[i][0]-1], P[L[i][1]-1])
ans = 0
for i in range(N):
    if tree.same(P[i], i+1):
        ans += 1
print(ans)