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

Solution (Python):
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)]
    
    
    
N,M = map(int, input().split())
P = [int(p) for p in 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.isSameGroup(P[i], i+1):
        ans += 1
        
print(ans)

Solution (Python):
n,m=map(int,input().split())
p=list(int(i)-1 for i  in input().split())
s=[list(int(i)-1 for i  in input().split()) for _ in range(m)]

a={i:i for i in range(n)}

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

for x,y in s:
    a[find(x)] = find(y)

ans=0

for i in range(n):
    if find(i)==find(p[i]):
        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 same(self, x, y):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
Permutation = list(map(int,input().split()))
Replace = [list(map(int,input().split())) for i in range(m)]

uf = UnionFind(n+1)
count = 0

for i in range(m):
    uf.union(Replace[i][0],Replace[i][1])

for i in range(1,n+1):
    if uf.same(Permutation[i-1],i):
        count += 1

print(count)

Solution (Python):
N, M = map(int, input().split())
p = [int(i) for i in 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)
    
ret = 0
visited = [False] * N
for i in range(N) :
    if visited[i] :
        continue
    
    q = [i]
    visited[i] = True
    a = [i+1]
    b = [p[i]]
    
    while q :
        cur = q.pop()
        for nex in v[cur] :
            if visited[nex] :
                continue
            q.append(nex)
            a.append(nex+1)
            b.append(p[nex])
            visited[nex] = True
    ret += len(set(a) & set(b))
print(ret)

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 = [int(x) for x in input().split()]
uf = UnionFind(N)
p = [int(x) for x in input().split()]
for _ in range(M):
  x,y = [int(x) for x in input().split()]
  uf.union(x-1,y-1)
ans = 0
for i in range(N):
  if i+1!=p[i] and uf.same(i,p[i]-1):
    ans +=1
  elif i+1==p[i]:
    ans += 1
print(ans)

Solution (Python):
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)]

def main():
    n,m = map(int,input().split())
    p = [int(x) for x in input().split()]
    uni = UnionFind(n)
    for i in range(m):
        a,b = map(int,input().split())
        uni.Unite(a,b)
    cnt = 0
    for i,p_ in enumerate(p):
        if uni.isSameGroup(i+1,p_):
            cnt += 1
    print(cnt)




if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
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 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
    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())
h = [int(i)-1 for i in input().split()]
dic1 = defaultdict(list)
dic2 = defaultdict(list)
u = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  u.unite(a-1,b-1)

for c in range(N):
  p = u.find(c)
  dic1[p] += [c]
  dic2[p] += [h[c]]
ans = 0
for p in dic1.keys():
  dic1[p].sort()
  dic2[p].sort()
  i = 0
  j = 0
  while i<len(dic1[p]) and j<len(dic2[p]):
    if dic1[p][i]==dic2[p][j]:
      i += 1
      j += 1
      ans += 1
    elif dic1[p][i]<dic2[p][j]:
      i += 1
    else:
      j += 1
    
print(ans)

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = 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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y) or x==y
		
def solve():
	n,_,*l=map(int,open(0).read().split())
	p=l[:n];xy=l[n:]
	ids=[0]*(n+1)
	for i,x in enumerate(p):ids[x]=i+1
	uf=UnionFind(n)
	for x,y in zip(*[iter(xy)]*2):uf.unite(x,y)
	print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
	
if __name__=="__main__":solve()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = 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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y) or x==y
		
def solve():
	n,m,*l=map(int,open(0).read().split())
	p=l[:n];xy=l[n:]
	ids=[0]*(n+1)
	for i in range(n):ids[p[i]]=i+1
	uf=UnionFind(n)
	for x,y in zip(*[iter(xy)]*2):uf.unite(x,y)
	print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
	
if __name__=="__main__":solve()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = 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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y)
		
n,m,*l=map(int,open(0).read().split())
p=l[:n];xy=l[n:]
ids=[0]*(n+1)
for i in range(n):
	ids[p[i]]=i+1
uf=UnionFind(n)
for x,y in zip(*[iter(xy)]*2):
	uf.unite(x,y)
print(sum(uf.isSame(i,ids[i])or i==ids[i] for i in range(1,n+1)))

Solution (Python):
N, M = map(int, input().split())
nums = list(map(int, input().split()))
ids = [0] * (N+1)
for i, n in enumerate(nums):
  ids[n] = i+1

class UnionFind():
  
  def __init__(self, n):
    self.par = list(range(n+1))
    self.rank = [0] * (n+1)

  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):
    xr = self.root(x)
    yr = self.root(y)
    if xr == yr:
      return
    if self.rank[xr] < self.rank[y]:
      self.par[xr] = yr
    else:
      self.par[yr] = xr
      if self.rank[xr] == self.rank[y]:
        self.rank[xr] += 1

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

i_tree = UnionFind(N)
  
for _ in range(M):
  x, y = map(int, input().split())
  i_tree.unite(x, y)
cnt = 0
for i in range(1, N+1):
  if i_tree.same(i, ids[i]):
    cnt += 1
print(cnt)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        '''
        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 と y のグループを結合
        '''
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        '''
        x と y が同じグループか否か
        '''
        return self.find(x) == self.find(y)

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = II()
p = III()
p = list(map(lambda x:x-1, p))
x,y = Line(M)

place = [0]*N
for i in range(N):
    place[p[i]] = i

uf = UF(N)
for i in range(M):
    uf.union(x[i]-1, y[i]-1)

ans = 0
for i in range(N):
    if uf.is_same(i,place[i]):
        ans += 1

print(ans)

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
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if x < y:
            self.par[ry] = rx
        else:
            self.par[rx] = ry
    
    def same(self, x, y):
        return self.root(x) == self.root(y)

n,m = map(int, input().split())
p = [int(x)-1 for x in input().split()]

ans = 0
UF = UnionFind(n)

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

for i in range(n):
    if UF.same(i,p[i]):
        ans += 1
print(ans)

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

class UnionFind:
  def __init__(self, n):
    self.tree = list(range(n))
    
  def root(self, n):
    if self.tree[n] == n:
      return n
    else:
      self.tree[n] = self.root(self.tree[n])
      return self.tree[n]
  
  def marge(self, x, y):
    if not self.root(x) == self.root(y):
      self.tree[self.root(y)] = self.root(x)
  

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

groups = [set() for _ in range(N)]
for i in range(N):
  groups[uf.root(i)].add(i)

ans = 0
for g in groups:
  if len(g) == 0: continue
  ans += len(set(P[i] for i in g) & g)

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)]

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

    def root(self, i):
        if(self.par[i] == i):
          return i
        else:
          self.par[i] = self.root(self.par[i])
          return self.par[i]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        self.par[x] = y

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

uf = UnionFind(n)
for x, y in xy:
    uf.union(x-1, y-1)
ans = 0
for i in range(n):
    if uf.same(i, p[i]-1):
        ans += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
p = [0] + [int(x) for x in input().split()]

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)

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

unionUF, unionp = [set() for _ in range(N+1)], [set() for _ in range(N+1)]
for i in range(1, N+1):
    temp = UF.find(i)
    unionUF[temp].add(i)
    unionp[temp].add(p[i])

ans = 0
for i in range(len(unionUF)):
    ans += len(unionUF[i] & unionp[i])
print(ans)

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
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
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 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




class UnionFind:
    def __init__(self, n):
        
        
        self.table = [-1] * 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 same(self, x, y):
        return self._root(x) == self._root(y)


    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
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2



n, m = LI()
p = LI()
U = UnionFind(n)
for x, y in LIR(m):
    U.union(x-1, y-1)


cnt = 0
for i in range(n):
    cnt += U.same(i, p[i]-1)



print(cnt)

Solution (Python):
n, m = map(int, input().split())
ps = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(m)]


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

    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


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

Solution (Python):
n, m = map(int, input().split())
ps = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(m)]


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

    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


uf = UnionFind(n)
for a, b in ls:
    uf.merge(a, b)
for i in range(1, n + 1):
    uf.get_root(i)
cs = uf.parents
s0 = {c: [] for c in set(cs[1:])}
s1 = {c: [] for c in set(cs[1:])}
for i in range(1, n + 1):
    c = cs[i]
    s0[c].append(ps[i - 1])
    s1[c].append(i)

res = 0
for c in set(cs[1:]):
    res += len(set(s0[c]) & set(s1[c]))
print(res)

Solution (Python):
N, M = map(int, input().split())
p = list(map(int, input().split()))
e = [list(map(int, input().split())) for _ in range(M)]
res = 0
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)]
uf = UnionFind(N)
childs = [[] for _ in range(N + 1)]
for i in range(M):
  uf.Unite(e[i][0], e[i][1])
for i in range(1, N + 1):
  childs[uf.Find_Root(i)].append(i)
for c in childs:
  temp = set([p[i - 1] for i in c])
  inter = temp & set(c)
  res += len(inter)
print(res)

Solution (Python):

class UnionFind:  
    def __init__(self, N):  
        self.parent = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

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

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

    def unite(self, x, y):  
        x, y = self.find(x), 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


def main():
    
    N, M, *A = map(int, open(0).read().split())
    P, E = A[:N], A[N:]
    U = UnionFind(N)  
    for v, u in zip(*[iter(E)] * 2):  
        U.unite(v, u)
    ans = sum(U.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


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

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

    n,m = LI()
    p = LI()
    for i in range(n):
        p[i] -= 1
    par = [i for i in range(n)]
    rank = [0]*n
    for i in range(m):
        x,y = LI()
        x -= 1
        y -= 1
        if root(x) != root(y):
            unite(x,y)
    ans = 0
    for i in range(n):
        if root(p[i]) == root(i):
            ans += 1
    print(ans)
    return


def B():

    return


def C():

    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    A()

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

for i in range(n):
    P[i] -= 1
for i in range(m):
    for j in range(2):
        X[i][j] -= 1

M = [[] for i in range(n)]

for i in range(m):
    M[X[i][0]].append(X[i][1])
    M[X[i][1]].append(X[i][0])

G = [0] * n
clr = 0

for i in range(n):
    if G[i] == 0 and len(M[i]) > 0:
        clr += 1
        G[i] = clr
        
        Q = M[i][:]
        st = 0
        while st < len(Q):
            if G[Q[st]] == 0:
                G[Q[st]] = clr
                for item in M[Q[st]]:
                    Q.append(item)

            st += 1



ans = 0
for i in range(n):
    if G[i] == 0 and i == P[i]:
        ans += 1

G2 = [[[], []] for i in range(clr+1)]

for i in range(n):
    G2[G[i]][0].append(i)
    G2[G[i]][1].append(P[i])



for i in range(1, clr+1):
    ans += len(G2[i][0]) * 2 - len(set(G2[i][0] + G2[i][1]))

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        
        self.par[ry] = rx
        return True

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

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

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

uf = UnionFind(N)
for x, y in XY:
    uf.unite(x-1, y-1)

c = 0
for i, p in enumerate(P):
    c += uf.is_same(i, p-1)

print(c)

Solution (Python):
import collections

def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    graph = collections.defaultdict(set)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)

    sets = []
    visited = set()
    idx = [-1 for _ in range(N+1)]
    j = 0
    for a in range(1, N+1):
        if a not in visited:
            visited.add(a)
            cur = [a]
            j += 1
            idx[a] = j
            while cur:
                temp = []
                for a in cur:
                    for b in graph[a]:
                        if b not in visited:
                            visited.add(b)
                            idx[b] = j
                            temp.append(b)
                cur = temp
    
    count = 0
    for i in range(N):
        if idx[i+1] == idx[p[i]]:
            count += 1
    return count



if __name__ == '__main__':
    print(main())

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] < 0:
            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 not x==y: 
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] 
                self.par[x] = y 
            else:
                self.par[x] += self.par[y]
                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) 

def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    P = list(map(int,input().split()))
    XY = [list(map(int,input().split())) for i in range(M)]
    A = UnionFind(N)
    
    for i in range(M):
        x,y = XY[i]
        A.union(x,y)
        
    ans = 0
    for i in range(N):
        j = i+1
        p = P[i]
        if A.same_check(j,p):
            ans += 1
    print(ans)
    
    
    
main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg
    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n,m=map(int, input().split())
    pd = [-1] * (n + 1)  
    p=list(map(int, input().split()))
    for _ in range(m):
        x,y=map(int, input().split())
        merge(x-1,y-1)
    ans=0
    for i in range(n-1,-1,-1):
        if get_group(i)==get_group(p[i]-1):
            ans+=1
    print(ans)

main()

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

class Union_find():
    def __init__(self, N):
        self.Group = [i for i in range(N)]
        
    def find(self,x):
        while self.Group[x] != x:
            x = self.Group[x]
        return x

    def Union(self,x,y):  
        if self.find(x) != self.find(y):
            self.Group[self.find(y)] = self.Group[self.find(x)] = min(self.find(y),self.find(x))

A = Union_find(N)

for x,y in S:
    A.Union(x-1,y-1)

ANS = 0

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

for i in range(N):
    if A.find(i) == A.find (P[i]):
        ANS += 1

print(ANS)