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):
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
xy = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

parents = [i for i in range(n)]
ranks = [0 for _ in range(n)]


def root(x):
    return x if x == parents[x] else root(parents[x])


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


def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


for x_, y_ in xy:
    unite(x_, y_)

count = 0
for i, p_ in enumerate(p):
    count += 1 if is_same(i, p_) else 0
print(count)

Solution (Python):
import sys


class UnionFind():
    def __init__(self, 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


N, M = map(int, input().split())
P = list(map(int, input().split()))
uf = UnionFind(N)
for IN in sys.stdin.readlines():
    x, y = map(int, IN.split())
    x -= 1; y -= 1
    uf.union(x, y)

ans = 0
for i, p in enumerate(P):
    p -= 1
    if i == p:
        ans += 1
    else:
        if uf.find(i) == uf.find(p):
            ans += 1

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]

    def find(self, x):
        if self.parents[x] == x:
            return x
        ret = self.parents[x] = self.find(self.parents[x])
        return ret

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.parents[root_x] = root_y
        return True


n, m = [int(i) for i in input().split()]
pp = [int(i)-1 for i in input().split()]
uf = UnionFind(n)
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    uf.union(x-1, y-1)

ans = 0
for i, p in enumerate(pp):
    if uf.is_family(i, p):
        ans += 1

print(ans)

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

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

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

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}


n,m=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(lambda x: int(x)-1,input().split())) for _ in range(m)]

UnionFind=UnionFind(n)
for x,y in XY:
    UnionFind.Unite(x,y)

cnt=0
for num,p in enumerate(P):
    if UnionFind.isSameGroup(num,p-1):
        cnt +=1

print(cnt)

Solution (Python):
n,m=map(int,input().split())
P=list(map(int,input().split()))
par=list(range(n+1))

def find(x):
    if par[x]==x:
        return x
    a=find(par[x])
    par[x]=a
    return a

for i in range(m):
    x,y=map(int,input().split())
    bx,by=find(x),find(y)
    par[y]=bx
    par[by]=bx

ans=0

for i in range(1,n+1):
    if find(i)==find(P[i-1]):
        ans+=1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
p = list( map(int, input().split()))

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

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

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

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

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

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

uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
for a,b in ab:
    a,b = a-1,b-1
    if uf.is_same(a,b): continue
    uf.union(a,b)

ans = 0

loop = [set() for i in range(n)]
for i in range(n):
    r = uf.root(i)
    loop[r].add(i)

for i in range(n):
    for j in loop[i]:
        if p[j]-1 in loop[i]: ans += 1

print(ans)

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    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 unite(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
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

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

n, m = na()
p = na()
uf = UnionFind(n)
for i in range(m):
    x, y = na()
    x -= 1
    y -= 1
    uf.unite(x, y)

d = dict()
for i in range(n):
    d[p[i] - 1] = i

ans = 0
for i in range(n):
    if uf.same(i, d[i]):
        ans += 1

print(ans)

Solution (Python):
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if get_root(i) == get_root(p[i] - 1):
        ans += 1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
p=list(map(int,input().split()))
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same (x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
parent=list(range(n))
rank=[0]*n
for i in range(m):
	x,y=map(int,input().split())
	unite(x-1,y-1)
ans=0
for i in range(n):
	if same(p[i]-1,i):
		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 unite(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 members(self,x):
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    
    def size(self,x):
        return -self.parents[self.find(x)]
    
    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 = [int(i)-1 for i in input().split()]
    dic = {i:idx for idx,i in enumerate(p)}   

    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        uf.unite(x,y)
    
    cnt = 0
    for i in range(n):
        if uf.same(dic[i],i):
            cnt += 1
    
    print(cnt)  
  
if __name__=='__main__':
    main()

Solution (Python):

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)


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

parent = [-1] * N
for _ in range(M):
    x, y = map(int, input().split())
    unite(parent, x - 1, y - 1)

result = 0
for i in range(N):
    if find(parent, i) == find(parent, p[i] - 1):
        result += 1
print(result)

Solution (Python):

class UnionFind:
    __slots__ = ["_data_size", "_first_index", "_parents"]

    def __init__(self, data_size: int, is_zero_indexed: bool = True) -> None:
        self._data_size = data_size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (data_size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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 main():
    N, _, *PXY = map(int, open(0).read().split())
    P, XY = PXY[:N], PXY[N:]
    uf = UnionFind(N, is_zero_indexed=False)
    for x, y in zip(*[iter(XY)] * 2):
        uf.unite(x, y)
    ans = sum(uf.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    for p in P:
        p -= 1
        if U.is_pare(p, P[p] - 1):
            res += 1
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N,M = map(int,input().split())

class UnionFind:
    def __init__(self, n):
        
        
        
        
        
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x):
        
        if self.parent[x] < 0:
            
            return x
        
        
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
    def size(self, x):
        
        
        return -self.parent[self.root(x)]
    def merge(self, x, y):
        
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
    def family(self,x): 
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): 
        return self.family(self.parent.index(min(self.parent)))
    def all_family(self): 
        P = {} 
        now = 0
        for i in range(self.n):
            if self.parent[i] < 0:
                P[i] = now
                now += 1
        C = [[] for _ in range(len(P))] 
        for i in range(self.n):
            C[P[self.root(i)]].append(i)
        return P,C


p = list(map(int,input().split()))
UF = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    UF.merge(x-1,y-1)

ans = 0
_,C = UF.all_family()
for i in range(len(C)):
    S = C[i]
    T = [p[i]-1 for i in S]
    ans += len(set(S).intersection(set(T)))

print(ans)

Solution (Python):
N,M = map(int,input().split())

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


def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]


def bool_same(x,y):
    return root(x) == root(y)


def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

p = [0] + list(map(int,input().split()))

for i in range(M):
    a,b = map(int,input().split())
    unite(a,b)

ans = 0
for i in range(1,N+1):
    if bool_same(i,p[i]):
        ans += 1

print(ans)

Solution (Python):
from collections import Counter
import bisect
N, M = map(int, input().split())
P = list(map(int, input().split()))
V = [[] for _ in range(N)]

for _ in range(M):
	x, y = map(int, input().split())
	V[x - 1].append(y - 1)
	V[y - 1].append(x - 1)
	

label = [-1] * N
label_num = 0

for i in range(N):
	if label[i] != -1: continue
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = label_num
		for adj in V[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	label_num += 1
	

label_set = [[] for _ in range(label_num)]
for i in range(N):
	label_set[label[i]].append(i)
	

def binary_search(val, lst):
	insert_place = bisect.bisect_left(lst, val)
	if len(lst) == insert_place: return False 
	return lst[insert_place] == val
	
ans = 0
for i in range(N):
	
	
	
	if binary_search(P[i] - 1, label_set[label[i]]):
		ans += 1
		
print(ans)

Solution (Python):
N, M = [int(i) for i in input().split()]
Pn = [int(i) for i in input().split()]
XYm = [[int(i) for i in input().split()] for _ in range(M)]

class UnionFind:
  def __init__(self, N, arr=None):
    if arr is None:
      self.roots = [-1 for i in range(N)]
      self.ranks = [0 for i in range(N)]
    else:
      self.roots = arr[:]
      self.ranks = [0 for i in range(N)]
            
  def root(self, i):
    root = self.roots[i]
    if root < 0:
      return i
    else:
      return self.root(root)
      
  def union(self, i, j):
    x = self.root(i)
    y = self.root(j)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.roots[x] = y
    else:
      self.roots[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1
  
  def same(self, i, j):
    return self.root(i) == self.root(j)
  
  def get_rank(self, i):
    root = self.root(i)
    return self.ranks[root]
  
uf = UnionFind(N)
for xy in XYm:
  x, y = xy
  uf.union(x-1, y-1)
  
count = 0
for i in range(N):
  count += 1 if uf.same(i, Pn[i]-1) else 0
print(count)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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()
P = LIST()
L = [LIST() for i in range(M)]

dic = defaultdict(list)
tree = UnionFind(N+1)
for a, b in L:
    tree.union(a, b)



ans = 0
for i in range(1, N+1):
    if tree.find(i) == tree.find(P[i-1]):
        ans += 1
print(ans)

Solution (Python):


n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
par = [i for i in range(n)]


def root(x):
    
    
    
    
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(a, b):
    if a > b:
        a, b = b, a
    ra, rb = root(a), root(b)
    if ra != rb:
        par[ra] = rb


for _ in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    union(x, y)

ans = 0
for i in range(n):
    ra, rb = root(i), root(p[i])
    if ra == rb:
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, 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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
ans = sum(u.same(p,i+1) for i,p in enumerate(p))
print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, 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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
ans = sum(1 if u.same(p,i+1) else 0 for i,p in enumerate(p))
print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, 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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
inf = [0]*(N+1)
for i in range(N):
  inf[p[i]] = i
ans = sum(1 if u.same(i,inf[i]+1) else 0 for i in range(1,N+1))
print(ans)

Solution (Python):
class UnionFind:
  def __init__(self, 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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
inf = {p[i]:i for i in range(N)}
ans = sum(1 if u.same(i,inf[i]+1) else 0 for i in range(1,N+1))
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self,x,y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot

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

uf = UnionFind(N)

for _ in range(M):
    x,y = map(int,input().split())
    uf.unite(x-1,y-1)

ans = 0

for i in range(N):
    if uf.find(i) == uf.find(P[i]-1):
        ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
p = list(map(int,input().split()))
for i in range(N): p[i] -= 1

par = [ i for i in range(N)]

def uf_root(a):
  if par[a] == a: return a
  par[a] = uf_root( par[a] )
  return par[a]

def uf_same(a,b):
  if (uf_root(a) ==uf_root(b)): return True
  return False

def uf_union(a,b):
  if (uf_same(a,b)): return
  a = uf_root(a)
  b = uf_root(b)
  par[a] = b
  return

for i in range(M):
  x,y = map(int, input().split())
  x -= 1
  y -= 1
  uf_union(x,y)

ans = 0
for i in range(N):
  if ( uf_same(i,p[i]) ):
    ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
p = list(map(int,input().split()))
for i in range(N): p[i] -= 1

par = [ i for i in range(N)]

def uf_root(a):
  if par[a] == a: return a
  par[a] = uf_root( par[a] )
  return par[a]

def uf_same(a,b):
  if (uf_root(a) ==uf_root(b)): return True

def uf_union(a,b):
  if (uf_same(a,b)): return
  a = uf_root(a)
  b = uf_root(b)
  par[a] = b
  return

for i in range(M):
  x,y = map(int, input().split())
  x -= 1
  y -= 1
  uf_union(x,y)

ans = 0
for i in range(N):
  if ( uf_same(i,p[i]) ):
    ans += 1
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,M=map(int,input().split())
p=tuple(map(lambda x: int(x)-1,input().split()))
l=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x: int(x)-1,input().split())
    l[x].append(y)
    l[y].append(x)
g=[None]*N
c=0
def hu(n,c):
    for i in l[n]:
        if g[i]==None:
            g[i]=c
            hu(i,c)
for i in range(N):
    if g[i]==None:
        g[i]=c
        hu(i,c)
        c+=1
a=0
for i in range(N):
    if g[i]==g[p[i]]:
        a+=1
print(a)

Solution (Python):
from collections import deque

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

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

for i in range(N):
    p[i] -= 1

data = [[] for i in range(N)]

for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    data[x].append(y)
    data[y].append(x)

group = [0] * N
count = 1
for i in range(N):
    if group[i] != 0:
        continue
    group[i] = count
    stack = deque([[i,i]])
    while stack:
        x = stack.pop()
        for y in data[x[1]]:
            if y == x[0] or group[y] != 0:
                continue
            stack.append([x[1],y])
            group[y] = count
    count += 1



p_inv = [0] * N

for i in range(N):
    p_inv[p[i]] = i

ans = 0

for i in range(N):
    if group[i] == group[p_inv[i]]:
        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 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 = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    u = UnionFind(N)
    for _ in range(M):
        x, y = [int(x) for x in input().split()]
        u.union(x - 1, y - 1)

    ans = 0
    for i, p in enumerate(P):
        if u.same(p - 1, i):
            ans += 1

    print(ans)






if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for _ in range(m)]
l=[i for i in range(n)]
def root(x):
  if x==l[x]:
    return x
  l[x]=root(l[x])
  return l[x]
for x,y in xy:
  a=root(x-1)
  b=root(y-1)
  if a!=b:
    l[b]=a
cnt=0
for i in range(n):
  if root(p[i]-1)==root(i):
    cnt+=1
print(cnt)