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):
import sys

n, m = map(int, sys.stdin.readline().split())
*p, = map(int, sys.stdin.readline().split())
xy = list(zip(*[map(int, sys.stdin.read().split())] * 2))

g = [[] for _ in range(n+1)]
for x, y in xy:
    g[x-1].append(y-1)
    g[y-1].append(x-1)

root = list(range(n))
height = [0] * n

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def unite(v, u):
    rv = find_root(v)
    ru = find_root(u)
    if root[rv] == root[ru]:
        return
    if height[rv] >= height[ru]:
        root[ru] = rv
        height[rv] = max(height[rv], ru+1)
    else:
        root[rv] = ru

def main():
    for x, y in xy:
        unite(x-1, y-1)

    for i in range(n):
        find_root(i)
    
    cnt = 0
    for i in range(n):
        cnt += (root[i] == root[p[i]-1]) & 1
    
    return cnt
    
if __name__ == '__main__':
    ans = main()
    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 = 10 ** 18
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 is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
A = LIST()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    uf.union(a, b)

ans = 0
for i, a in enumerate(A):
    
    if uf.is_same(i+1, a):
        ans += 1
print(ans)

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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    n, m = map(int, input().split())
    p = tuple(map(int, input().split()))
    uf = UF_tree(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x, y)

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

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

root = [i for i in range(N + 1)]
comp_size = [1] * (N + 1)

def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if sx >= sy:
    comp_size[rx] += comp_size[ry]
    root[ry] = root[rx]
  else:
    comp_size[ry] += comp_size[rx]
    root[rx] = root[ry]

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


answer = 0
for i in range(N):
  if root_find(P[i]) == root_find(i + 1):
    answer += 1

print(answer)

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    P = [int(i)-1 for i in input().split()]
    for i in range(M):
        x, y = (int(i)-1 for i in input().split())
        unite(x, y)
    ans = 0
    for i, p in enumerate(P):
        if is_same_group(i, p):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

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

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

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M=MI()
    P=LI_()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    XY=LLIN_(M)
    for x,y in XY:
        unite(x,y)

    ans = 0
    for i,a in enumerate(P):
        ans += get_root(i)==get_root(a)
    print(ans)
if __name__ == '__main__':
    main()

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


n, m = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))


class UnionFind:
    def __init__(self, num):
        self.parent = list(range(num))

    def get_root(self, node):
        root = self.parent[node]
        if root == node:
            return root
        else:
            root = self.get_root(root)
            self.parent[node] = root
            return root

    def are_in_same_union(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return True
        else:
            return False

    def unite(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return
        self.parent[root2] = root1


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


count = 0
for i in range(n):
    num = P[i]
    if num == i:
        count += 1
    else:
        if uf.are_in_same_union(i, num):
            count += 1

print(count)

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

tree = UnionFind(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    tree.union(x, y)

ans = 0
for i, p in enumerate(P, start=1):
    if tree.isSameRoot(i, p):
        ans += 1
print(ans)

Solution (Python):

n, m = map(int, input().split())
p = list(map(int, input().split()))
x, y = [0] * m, [0] * m
reach = [[] for _ in range(n + 1)]
for i in range(m):
    x[i], y[i] = map(int, input().split())
    reach[x[i]].append(y[i])
    reach[y[i]].append(x[i])


check = [0] * (n + 1)
color = [-1] * (n + 1)
c = -1

for i in range(n + 1):
    if check[i] == 1:
        pass
    else:
        c += 1
        check[i] = 1
        stack = reach[i]
        color[i] = c
        while len(stack) >= 1:
            tmp = stack.pop(-1)
            color[tmp] = c
            check[tmp] = 1
            tmp_list = reach[tmp]
            for i in range(len(tmp_list)):
                if check[tmp_list[i]] == 0:
                    stack.append(tmp_list[i])
                    check[tmp_list[i]] = 1
                else:
                    pass

color.pop(0)


ans_list = [0] * n
for i in range(n):
    ans_list[i] = color[p[i] - 1]


ans = 0
for i in range(n):
    if color[i] == ans_list[i]:
        ans += 1
print(ans)

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

n, m = [ int(v) for v in input().split() ]
num = [ int(v)-1 for v in input().split() ]
parent_list = [ i for i in range(n) ]

def root(x):
    while parent_list[x] != x:
        parent_list[x] = parent_list[parent_list[x]]  
        x = parent_list[x]   
    return x

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    ra, rb = root(a), root(b)
    if ra != rb:
        parent_list[ra] = rb
        
ans_list = []
for i, v in enumerate(num):
    if root(i) == root(v):
        ans_list.append(True)
    else:
        ans_list.append(False)

print(ans_list.count(True))

Solution (Python):
n,m=map(int,input().split())
 
a=[int(i) for i in range(n)]

def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
p=list(int(i)-1 for i  in input().split())
pp=p
ans=0

s=[list(int(i)-1 for i  in input().split()) for _ in range(m)]
for x, y in s:
    unite(a,x,y)
for i in range(n):
    if find(a,i)==find(a,pp[i]):
        ans+=1

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (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 same_check(self,x,y):
        return self.find(x) == self.find(y)
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        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

n,m = map(int,input().split())
ps = list(map(int,input().split()))
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x,y)

cnt = 0
for i,j in enumerate(ps):
    if uf.same_check(i+1 , j):
        cnt += 1
print(cnt)

Solution (Python):
N,M=map(int,input().split())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

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

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

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

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

c=0
for i in range(N):
	if same(i,e[i]):
		c+=1

print(c)

Solution (Python):
class UnionFind():
  def __init__(self, N):
    self.par = [i for i in range(N)]
 
  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    self.par[self.root(y)] = self.root(x)
    
  def same(self, x, y):
    return self.root(x) == self.root(y)

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.unite(x-1, y-1)
  
r = 0
for i in range(N):
  r += uf.same(i, p[i] - 1)
print(r)

Solution (Python):
class UnionFind():
  def __init__(self, N):
    self.par = [i for i in range(N)]
 
  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    self.par[self.root(y)] = self.root(x)
    
  def same(self, x, y):
    return self.root(x) == self.root(y)

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.unite(x-1, y-1)
  
r = 0
for i in range(N):
  r += uf.same(i, p[i] - 1)
print(r)

Solution (Python):

import sys

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 solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(x[i]-1,y[i]-1)

    answer = 0

    for j in range(N):
        if uf.same(p[j]-1,j):
            answer +=1        
        
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    p = [int(next(tokens)) for _ in range(N)]  
    x = [int()] * (M)  
    y = [int()] * (M)  
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    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 examD():
    N, M = LI()
    P = LI()
    uf = UnionFind(N)
    for i in range(M):
        x, y = LI()
        if not uf.same(x - 1, y - 1):
            uf.union(x - 1, y - 1)
    ans = 0
    for i in range(N):
        if uf.same(P[i]-1,i):
            ans +=1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):




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

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


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


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


def same(nx, ny):
    return root(nx) == root(ny)


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

ans = 0
for i in range(n):
    if same(i, arr[i]):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (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 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_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split(' '))
P = [int(c) for c in input().split(' ')]

uft = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split(' '))
    x -= 1
    y -= 1
    uft.union(x, y)

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

print(ans)

Solution (Python):
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]
par = [i for i in range(N+1)]
rank = [0] * (N+1)
 
def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]
 
def union(x,y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
 
def check_same(x,y):
    return find(x) == find(y)
 
for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    union(x,y)
ans = 0
for i in range(1,N+1):
    if find(i) == find(P[i-1]):
        ans += 1
print(ans)

Solution (Python):
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]
par = [i for i in range(N+1)]
rank = [0] * (N+1)

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

def union(x,y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[x] = y
        if rank[x] == rank[y]:
            rank[x] += 1

def check_same(x,y):
    return find(x) == find(y)

for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    union(x,y)
ans = 0
for i in range(1,N+1):
    if find(i) == find(P[i-1]):
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(1000000)
d1=defaultdict(list)
d2=defaultdict(list)
n,m=map(int,input().split())
l=list(map(int,input().split()))
la=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  la[a].append(b)
  la[b].append(a)
lb=[0 for i in range(n+1)]
def dfs(x,y):
  if lb[x]!=0:
    return
  else:
    lb[x]=y
    s=la[x]
    if s==[]:
      pass
    else:
      for i in s:
        dfs(i,y)
c=1
for i in range(1,n+1):
  dfs(i,c)
  c+=1
lc=set(lb)
for i in range(1,n+1):
  d1[lb[i]]+=[i]
  d2[lb[i]]+=[l[i-1]]
ans=0
for i in d1:
  d11=d1[i]
  d12=d2[i]
  for j in d12:
    index=bisect.bisect_right(d11,j)
    if d11[index-1]==j:
      ans+=1
print(ans)

Solution (Python):

class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = Uf(N+1)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)
    ans = 0
    for i, p in enumerate(P, 1):
        if uf.same(i, p):
            ans += 1
    print(ans)

main()

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N, M = list(map(int, input().split()))
P = list(map(int, input().split()))
L = [None]*N
for l, p in enumerate(P):
    L[p-1] = l
uf = UF(N)
for _ in range(M):
    x, y = list(map(int, input().split()))
    uf.union(x-1, y-1)

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    perm=list(map(lambda x:int(x)-1,input().split()))
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    
    cnt=[0]
    comp=[-1]*n
    def dfs(v)->NoneType:
        if(comp[v]!=-1): return
        cnt[0]+=1
        comp[v]=cnt[0]
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(comp[nv]!=-1): continue
                comp[nv]=cnt[0]
                Q.append(nv)

    for v in range(n): dfs(v)
    print(sum(1 for v in range(n) if(comp[v]==comp[perm[v]])))
resolve()

Solution (Python):
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
ps = ril()
ls = rils(m)

uf = UnionFind(n)
for a, b in ls:
    uf.merge(a - 1, b - 1)
res = 0
for i in range(n):
    p0 = uf.get_root(i)
    p1 = uf.get_root(ps[i] - 1)
    if p0 == p1:
        res += 1
print(res)