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
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

n,m = li()
p = list(li_())
xy = []
for _ in range(m):
    xy.append(tuple(li_()))
    
uf = UnionFind(n)

for x,y in xy:
    uf.unite(x,y)
    
rtnode = {i:set() for i in range(n)}
number = {i:set() for i in range(n)}

for i in range(n):
    uf.find(i)
    rtnode[uf.par[i]].add(i)
    number[uf.par[i]].add(p[i])
    
ans = 0
for i in range(n):
    ans += len(rtnode[i] & number[i])
    
print(ans)

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y in src:
    x,y = x-1,y-1
    if uf.is_same(x,y): continue
    uf.unite(x,y)

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

ans = 0
for i in range(N):
    for j in bags[i]:
        if P[j]-1 in bags[i]:
            ans += 1
print(ans)

Solution (Python):
class Union_find:
    def __init__(self,n):
        self.group=[i for i in range(n)]
    
    def root(self,x):
        if(self.group[x]==x):
            return x
        else:
            tmp=self.root(self.group[x])
            self.group[x]=tmp
            return tmp
    
    def make(self,x,y):
        self.group[self.root(x)]=self.root(y)
    
    def judge(self,x,y):
        if(self.root(x)==self.root(y)):
            return True
        else:
            return False


n,m=map(int,input().split())
T=Union_find(n+1)
P=list(map(int,input().split()))

for _ in range(m):
    
    x,y=map(int,input().split())
    T.make(x,y)


ans=0

for i in range(n):
    if(T.judge(P[i],i+1)):
        ans+=1

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self._par = [i for i in range(n)]
        self._rnk = [0 for _ in range(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._rnk[x] < self._rnk[y]:
            x, y = y, x

        if self._rnk[x] == self._rnk[y]:
            self._rnk[x] += 1

        self._par[y] = x

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

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

print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

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

ans = 0
for i, n in enumerate(p, 1):
    ans += g.find(i) == g.find(n)
print(ans)

Solution (Python):
class UnionFind():
    def run(self, N, M, p, x):
        '''Union find(ランクなし)'''
        
        self.part = []
        for i in range(N+1):
            self.part.append(i) 
        
        for i in range(M):
            self.union(x[i][0], x[i][1])
        cnt = 0
        for i in range(1, N+1):
            if self.root(i) == self.root(p[i-1]):
                cnt += 1
        return cnt

    def root(self, x):
        if self.part[x] == x:
            return x
        else:
            
            self.part[x] = self.root(self.part[x])
            return self.part[x]
    
    def union(self, x, y):
        x_root = self.root(self.part[x])
        y_root = self.root(self.part[y])
        if x_root == y_root:
            pass
        else:
            self.part[x_root] = y_root


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    x = []
    for i in range(M):
        x.append(list(map(int, input().split())))
    obj = UnionFind()
    print(obj.run(N, M, p, x))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
par = list(range(n+1))

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

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

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    if i in paths.keys():
        stack = deque(paths[i])
        cluster = set([i]+paths[i])
    else:
        stack = []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in cluster:
                stack.append(k)
                cluster.add(k)
    path_id += 1


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

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


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

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

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

        if x == y:
            return

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

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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


UF.all_find()

ans = 0
for index, number in P:
    ans += UF.same(index, number - 1)

print(ans)

Solution (Python):
class UF:
    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 find(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
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for _ in range(m)]
x=[t[0] for t in xy]
y=[t[1] for t in xy]

uf=UF(n)
for i in range(m):
    uf.union(x[i]-1,y[i]-1)
ans=0
for i in range(n):
    if p[i]==i+1:
        ans+=1
    elif uf.find(p[i]-1,i):
        ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for _ in range(size)]

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

    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


N,M = map(int,input().split())
p = list(map(int,input().split()))
t = UnionFind(N+1)
for i in range(M):
    x,y = map(int,input().split())
    t.union(p[x-1],p[y-1])

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

print(ans)

Solution (Python):
def searchP(dic,x):
    p =dic[x]['p'] 
    if p==x:
        return x
    dic[x]['p']= searchP(dic,p)
    return dic[x]['p']

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

dic={i:{'p':i,'length':0} for i in range(1,N+1)}
for i in range(M):
    x,y=list(map(int,input().split()))
    x=searchP(dic,x)
    y=searchP(dic,y)
    
    if dic[x]['length']<dic[y]['length']:
        dic[x]['p']=y
    else:
        dic[y]['p']=x

group={}
ans=0
for i,v in enumerate(arr):
    if searchP(dic,v)== searchP(dic,i+1):
        ans+=1
print(ans)

Solution (Python):
from collections import defaultdict

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

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

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            if self.rank[a] == self.rank[b]:
                self.rank[a] += 1
            self.parent[b] = a


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

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

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

print(num)

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)]
rank = [0]*n

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

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

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

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

Solution (Python):
N,M=map(int,input().split())
P=[int(i)-1 for i in input().split()]
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(a[i],b[i])
ans=0
for i in range(N):
    if same(i,P[i]):
        ans+=1
print(ans)

Solution (Python):
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n)}
def U(x):
  if D[x]!=x:
    D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x-1)]=U(y-1)
print(sum(U(i)==U(p-1)for i,p in enumerate(P)))

Solution (Python):
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:

			if self.tree[xr]==self.tree[yr]:
				self.tree[xr]-=1
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Solution (Python):
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Solution (Python):
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			return self.find(self.tree[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Solution (Python):
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			return self.find(self.tree[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Solution (Python):
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			return self.find(self.tree[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		if a.find(x)==a.find(li[x]):
			ans+=1
	return ans
print(main())

Solution (Python):
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n+1)}
def U(x):
  if D[x]!=x:D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x)]=U(y)
print(sum(U(i)==U(p)for i,p in enumerate(P,1)))

Solution (Python):
I=lambda:[int(i) for i in input().split()]
n, m = I()
P = I()
D = {i:i for i in range(n+1)}

def U(x):
  if D[x] != x:
    D[x] = U(D[x])
  return D[x]

for _ in range(m):
  x, y = I()
  D[U(x)] = U(y)

print(sum(U(i)==U(p) for i, p in enumerate(P,1)))

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

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

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

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

Solution (Python):
from collections import defaultdict
import sys
sdin = sys.stdin.readline

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
        else:
            self.par[ry] = rx
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

    

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


root_node = defaultdict(list)

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

for i in range(N):
    uf.find(i)
    
par = uf.par

for i,root in enumerate(par):
    root_node[root].append(i)
    
ans = 0
for node_list in root_node.values():
    num_list = []
    for i in node_list:
        num_list.append(P[i]-1)
    
    ans += len(set(node_list)&set(num_list))
            
print(ans)

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

par = [i for i in range(N)]
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

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

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

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

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

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

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

for x, y in s:
    a[root(x)] = root(y)
    
ans = 0
for i in range(n):
    if root(i) == root(p[i]):
        ans += 1

print(ans)

Solution (Python):
def root(x):
    if(group[x] == x):
        return(x)
    else:
        group[x] = root(group[x])
        return(group[x])


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

    if(rank[x] < rank[y]):
        group[x] = y
    else:
        group[y] = x
        if(rank[x] == rank[y]):
            rank[x] += 1


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


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

group = [i for i in range(N)]
rank = [0 for i in range(N)]

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


ans = 0
for i in range(N):
    if(same(i, N_list[i]) is True):
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):	
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	
		return table[x]

def Union(x,y):	
	x = Find(x)
	y = Find(y)

	if x == y:
		return

	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False

N,M = inpl()

table = [i for i in range(N)]	
rank  = [1 for i in range(N)]	

pp = inpl()

for i in range(M):
	x,y = inpl()
	x -= 1
	y -= 1
	Union(x,y)

ans = 0
for i in range(N):
	if Check(pp[i]-1,i):
		ans += 1

print(ans)

Solution (Python):
from collections import defaultdict
import sys
sdin = sys.stdin.readline

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

    

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


root_node = defaultdict(list)

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

for i in range(N):
    uf.find(i)
    
par = uf.par

for i,root in enumerate(par):
    root_node[root].append(i)
    
ans = 0
for node_list in root_node.values():
    num_list = []
    for i in node_list:
        num_list.append(P[i]-1)
    
    ans += len(set(node_list)&set(num_list))
            
print(ans)

Solution (Python):

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


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    x = Find(x)
    y = Find(y)
    a = rank[x]
    b = rank[y]
    forest[x] = y


def Find(x):
    if forest[x] != x:
        rank[x] = 1
        forest[x] = Find(forest[x])
        return forest[x]
    else:
        return x
    
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    
    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)

Solution (Python):


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

class UnionFind3:
    def __init__(self, size):
        
        
        self.table = [-1 for i in range(size)]

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

    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return 1
        return 0


cnt = 0
tree = UnionFind3(n)
for i in range(m):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)

for i in range(n):
    a = tree.find(i)
    b = tree.find(List[i]-1)
    if a == b:
        cnt += 1

print(cnt)

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

def m():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    color = [-1] * (n+1)

    def dfs(v, c):
        s = []
        s.append(v)
        color[v] = c
        while len(s) != 0:
            a = s.pop()
            for elem in g[a]:
                if color[elem] == -1:
                    dfs(elem, c)

    k = 0
    for i in range(1, n):
        if color[i] == -1:
            dfs(i,k)
            k +=1
    ans = 0
    for i in range(n):
        if color[p[i]] == color[i+1]:
            ans +=1
    return ans

print(m())

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0

y = [-1] * n
for i in range(0,n):
  if y[i] == -1:
    y[i] = i
  c = l[i+1]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = y[i]
    for j in range(len(l[z])):
      if y[l[z][j]-1] == -1:
        c.append(l[z][j])
    l[z] =[]
    
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)

Solution (Python):
def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


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


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)

Solution (Python):
import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
p.insert(0,0)
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

link = [[] for _ in  range(N+1)]
for i in range(M):
  x = pairs[i][0]
  y = pairs[i][1]
  link[x].append(y)
  link[y].append(x)


ans = 0
visited = set()

for i in range(1, N+1):

  
  if i in visited:
    continue
  
  
  
  linked = set()

  
  todo = [i]
  while todo:

    
    cur = todo.pop()
    for dest in link[cur]:

      
      if dest not in linked:
        linked.add(dest)
        todo.append(dest)

  
  ans += len(linked & set(p[n] for n in linked))
  
  visited |= linked


for i in set(range(1,N+1)) - visited:
  ans += i == p[i]

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
        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:
            self.par[x]=y
 
n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]
 
uf=UnionFind(n)
for pi in pair:
    uf.unite(pi[0],pi[1])
 
cnt=0
for i, pi in enumerate(p):
    if uf.same(i,pi):
        cnt+=1
print(cnt)