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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heapify,heappop,heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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]

n,m = inpl()
p = inpl()
uf = UnionFind(n)
for i in range(m):
    a,b = inpl()
    uf.union(a-1,b-1)
res = 0
for i in range(n):
    if uf.find(p[i]-1) == uf.find(i):
        res += 1
print(res)

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())
x=UnionFind(n)
lists=list(map(int,input().split()))          
for i in range(m):
    a,b=map(int,input().split())
    x.union(a,b)
uselist=[0]*n
for i in range(1,n+1): 
    uselist[i-1]=x.find(i)
grouplist=[[]for i in range(n+1)]
sublist=[[]for i in range(n+1)]
for i in range(n):
    grouplist[uselist[i]].append(lists[i])
    sublist[uselist[i]].append(i+1)
ans=0
for i in range(n+1):
    x=set(grouplist[i]) & set(sublist[i])
    ans+=len(x)
print(ans)

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

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

def unite(a,b,root,depth):
    A = find(a,root)
    B = find(b,root)
    if A == B:
        return
    elif depth[A] > depth[B]:
        root[B] = A
        depth[A] += depth[B]
    else:
        root[A] = B
        depth[B] += depth[A]
for i in range(M):
    x,y = map(int,input().split())
    unite(x-1,y-1,root,depth)

order = [-1 for _ in range(N)]
for i in range(N):
    order[p[i]-1] = find(i,root)
count = 0
for i in range(N):
    if order[i] == root[i]:
        count += 1
print(count)

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())
A = list(map(int, input().split()))
O = [list(map(int, input().split())) for _ in range(M)]

ope = UnionFind(N)

for i in range(M):
	ope.Unite(O[i][0], O[i][1])

cnt = 0

for i in range(N):
	if ope.isSameGroup(i+1, A[i]):
		cnt += 1

print(cnt)

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 = list(map(int,input().split()))
for i in range(N): 
  P[i] = P[i]-1
  
union = UnionFind(N)
for i in range(M):
  x,y = map(int,input().split())
  union.Unite(x-1,y-1)

ans = 0
for i in range(N):
  if(union.isSameGroup(P[i],i) == True): ans += 1 
print(ans)

Solution (Python):
import sys
import collections
class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  

    def root(self, x):  
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  
            return self.parent[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 size(self, x):  
        return -self.parent[self.root(x)]
sys.setrecursionlimit(100000000)

N,M = list(map(int,input().split(" ")))
Ps =  list(map(int,input().split(" ")))
u = UnionFind(N)
for i in range(M):
    a,b = list(map(int, input().split(" ")))
    u.merge(a,b)
ans = 0
for i in range(1,N + 1):
    if u.root(i) == u.root(Ps[i-1]):
        ans += 1
print(ans)

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

def root(n):
    O = {n}
    while True:
        if tree[n] == n:
            for o in O:
                tree[o] = n
            return n
        n = tree[n]
        O.add(n)

for i in range(M):
    x,y = map(lambda x: int(x)-1,input().split())
    rx = root(x)
    ry = root(y)
    if rx == ry:
        continue
    tree[rx] = ry

print(sum(map(lambda x: root(x)==root(P[x]),range(N))))

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(i) for i in input().split()]

uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
ans=0
for i in range(n):
    if uf.same_check(p[i],i+1):
        ans+=1
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=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.root = [-1]*(n+1)
        self.cnt = 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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

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






        
    
uf = UnionFind(N)
for x,y in xy:
    uf.union(x-1,y-1)
    
for i in range(N):
    uf.find(i)
    
idxlist = [[] for _ in range(N)]

for i,t in enumerate(uf.par):
    idxlist[t].append(i)
    
import bisect
ans = 0
for idxs in idxlist:
    for idx in idxs:
        tmpidx = bisect.bisect_left(idxs,P[idx]-1)
        if tmpidx >= len(idxs):continue
        if idxs[tmpidx] == P[idx]-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[y] = x
        else:
            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 = list(map(int, input().split()))
  xy = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N+1)
  for x, y in xy:
    U.Unite(x, y)
  ans = 0
  for i in range(1, N+1):
    if U.isSameGroup(i, p[i-1]):
      ans += 1
  print(ans)


if __name__ == "__main__":
  main()

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

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

    nodes = [Node() for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(nodes[a], nodes[b])
    
    ans = 0
    for i in range(N):
        if same_tree(nodes[i], nodes[p[i]-1]):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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())
	xy=l[n:]
	ids=[0]*(n+1)
	for i in range(n):ids[l[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 uf():
    def __init__(self,n):
        self.root = [-1] * (n+1)

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

    def unite(self,x,y):
        rootx = self.findroot(x)
        rooty = self.findroot(y)
        if rootx == rooty:
            return
        else:
            self.root[rootx] += self.root[rooty]
            self.root[rooty] = rootx
            return

    def is_same_group(self,x,y):
        return self.findroot(x) == self.findroot(y)

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

uf = uf(N)

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

count = 0
for n in range(N):
    if uf.is_same_group(P[n],n+1):
        count += 1

print(count)

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(i) for i in input().split()]
uf = UnionFind(N)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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


E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)


def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1


G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)


ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)

Solution (Python):

import sys
def input():
	return sys.stdin.readline().strip()




class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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

num = 0
for i in range(N):
	if UF.root(i) == UF.root(p[i] - 1):
		num += 1

print(num)

Solution (Python):


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False



def dsUpdate(ds):
    for x0 in ds:
        x = x0
        while ds[x] != x:
            x = ds[x]

        root = x
        x = x0

        while ds[x] != root:
            y = ds[x]
            ds[x] = root
            x = y


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

    ds = {x:x for x in range(1, N+1)}
    for x, y in [map(int, input().split()) for _ in range(M)]:
        dsUnion(ds, x, y)
        
    dsUpdate(ds)

    Q = {}
    for x, root in ds.items():
        if not root in Q:
            Q[root] = set()

        Q[root].add(x)

    cnt = 0

    for q in Q.values():
        p = set(P[x-1] for x in q)
        cnt += len(q&p)

    print(cnt)



if __name__ == '__main__':
    main()

Solution (Python):

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


N, M = map(int,input().split())
P = list(map(int, input().split()))
X = [0] * M
Y = [0] * M

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

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

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

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

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

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count


uf = UnionFind(N)
for i in range(M):
    uf.unite(X[i], Y[i])



ans = 0
for i in range(len(P)):
    p = P[i]-1
    if i==p or uf.same(i, p):
        ans += 1

print(ans)

Solution (Python):
class uf_tree():

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

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    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 same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False

n,m = map(int,input().split())
arr = list(map(int,input().split()))
tree = uf_tree(n)
for i in range(m):
    a,b = map(int,input().split())
    tree.unite(a-1,b-1)

ans = 0
for i in range(n):
    if tree.same(arr[i]-1,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)]

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

uf = UnionFind(2*N)
for i in range(N):
    
    uf.Unite(N+i,p[i] -1)
for i in range(M):
    uf.Unite(N+xy[i][0]-1,N+xy[i][1] -1)
ans = 0
for i in range(N):
    if uf.isSameGroup(N+i,i):
        ans += 1
print(ans)

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

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

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

   def union(self, x, y):
       x, y = self.find(x), self.find(y)
       if (x == y):
           pass
       else:
           self.parent[x] = self.parent[y]
           self.parent[y] = x

   def isgroup(self, x, y):
       return True if self.find(x) == self.find(y) else False


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

uf = UnionFind(n+1)

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

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

print(count)

Solution (Python):

import sys
input = sys.stdin.readline


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 = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    U = UnionFind(N)  
    for v, u in E:  
        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):

import sys
input = sys.stdin.readline


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 = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    U = UnionFind(N)  
    for v, u in E:  
        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):

import sys

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


def dfs(v: int, color: int) -> None:
    group[v] = color  
    for u in G[v]:  
        if not group[u]:  
            dfs(u, color)


def main():
    
    global G, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    group = [0] * (N + 1)
    color = 1
    for v in range(1, N + 1):  
        if not group[v]:
            dfs(v, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

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


def dfs(v: int, color: int) -> None:
    seen[v] = 1  
    group[v] = color
    for u in G[v]:  
        if not seen[u]:  
            dfs(u, color)


def main():
    
    global G, seen, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    seen, group = [0] * (N + 1), [0] * (N + 1)
    color = 1
    for i in range(1, N + 1):  
        if not seen[i]:
            dfs(i, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

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 same(self, x, y):
        return self.root(x) == self.root(y)

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

        if x == y:
            return
        
        self.par[x] = y
        return


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

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


if __name__ == '__main__':
    main()

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
    else:
        par[x] =root(par[x])
        return par[x]
def union(x,y):
    x= root(x)
    y= root(y)
    if x==y:
        return
    else:
        par[x]=y

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

for i in range(n):
    root(i)

dual = [(x,y) for x,y in zip(p,par)]
dual.sort(key=lambda x:x[0])
ans = 0
for i in range(n):
    if dual[i][1]==par[i]:
        ans+=1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(lambda x: int(x)-1, input().split()))
    parent = [k for k in range(N)]

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

    def unite(x,y):
        parent[find(x)] = find(y)

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

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

if __name__ == '__main__':
    main()

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

class Unionfind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]
        self.rank = [0] * (n)
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
          
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
U = Unionfind(n+1)
pn = [0]+[int(i) for i in input().split()]
cnt = -1
for i in range(m):
  a,b = map(int,input().split())
  U.union(a,b)
for i,v in enumerate(pn):
  if U.is_same(i,v):
    cnt += 1
print(cnt)