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 uf():
    def __init__(self,n):
        self.n=n
        self.pa=[-1]*n
    def find(self,x):
        if self.pa[x]<0:
            return x
        else:
            self.pa[x]=self.find(self.pa[x])
            return self.pa[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
        	return True
        else:
            if self.pa[x]>self.pa[y]:
                x,y=y,x
            self.pa[x]+=self.pa[y]
            self.pa[y]=x
            return True
    def same(self,x,y):
        return self.find[x]==find.pa[y]
    def size(self,x):
        return -self.pa[self.find(x)] 
n,m=map(int,input().split())
import sys
input=sys.stdin.readline
l=list(map(int,input().split()))
uf=uf(n)
for i in range(m):
    a,b=map(int,input().split())
    uf.unite(a-1,b-1)
d=dict()
for i in range(n):
    if uf.find(i) in d:
        d[uf.find(i)].add(i)
    else:
        d[uf.find(i)]=set([i])
for x in d:
  for y in d[x]:
    if l[y]-1 in d[x]:
      pass
    else:
      n-=1
print(n)

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 = map(int, input().split())
p = list(map(int, input().split()))
uf = UnionFind(n)
ans = 0

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

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

print(ans)

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

    def root(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.root(self.parent[x])
        return self.parent[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
        if self.siz[x] < self.siz[y]: 
            x,y = y,x
        self.parent[y] = x
        self.siz[x] += self.siz[y]

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

n,m = map(int,input().split())
p = [int(i)-1 for i in input().split()]
ds = DisjointSets(n)
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    ds.unite(x,y)
ans = 0
for i,p in enumerate(p):
    if ds.same(i,p): ans += 1
print(ans)

Solution (Python):
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 size(x):
        return -par[root(x)]

    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
if __name__ == '__main__':
    n, m=map(int, input().split())
    p=[int(i)-1 for i in input().split()]
    uf = UnionFind(n)
    for i in range(m):
        a,b=map(int, input().split())
        uf.unite(a-1,b-1)
    ans = 0
    for i in range(n):
        if uf.is_same(p[i], i):
            ans+=1
    print(ans)

Solution (Python):

import sys
input = sys.stdin.readline




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




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


A = UnionFind(N)
for x,y in XY:
    A.unite(x,y)


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

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

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

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

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
N, M = map(int, input().split())
X = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    UF.union(a, b)
ans = 0
for i in range(N):
    if UF.same_check(X[i], i+1):
        ans += 1
print(ans)

Solution (Python):

def find(x):
    if par[x] < 0:
        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 False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


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


def size(x):
    return -par[find(x)]


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

par = [-1] * N
P = list(map(int, input().split()))
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

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

print(ans)

Solution (Python):


class UF:
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) 
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        
        
        
        
        
        if self.size(a_par) < self.size(b_par): 
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

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



def main():
    n,m = map(int,input().split())
    num_lst = [0] + list(map(int,input().split()))
    uf = UF(n) 
    for _ in range(m):
        x,y = map(int,input().split())
        uf.union(x,y) 

    counter = 0 
    for i,j in enumerate(num_lst[1:]):
        if uf.is_same(i+1,j): 
            counter += 1      
    print(counter)

if __name__ == '__main__':
    main()

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

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


def find(v):
    visit = []
    while dfind[v] != v:
        visit.append(v)
        v = dfind[v]

    for i in visit:
        dfind[i] = v

    return v


def union(v0, v1):
    g0, g1 = find(v0), find(v1)
    g0, g1 = min(g0, g1), max(g0, g1)

    if g0 != g1:
        dfind[g1] = g0


for x, y in xy:
    union(x - 1, y - 1)


nmatch = 0
for i, p in enumerate(ps):
    if find(i) == find(p):
        nmatch += 1

print(nmatch)

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

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

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

unionfind = UnionFind(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    unionfind.union(x, y)
ans = 0
for i in range(N):
    if i + 1 != p[i]:
        if unionfind.same(p[i], i + 1):
            ans += 1
    else:
        ans += 1
print(ans)

Solution (Python):


import sys






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    
            self.rank = [0] * self.n    
            self.group_size = [1] * self.n    
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            
            if shallow_root == deep_root:
                return False
            
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])
    
    
    n, m = mi()
    P = lmi_0()

    uf = UnionFindTree(n)
    for _ in range(m):
        x, y = mi_0()
        uf.union(x, y)
    
    
    groups = [[] for _ in range(n)]
    for i in range(n):
        groups[uf._find_set(i)].append(i)
    
    cnt = 0
    for g in groups:
        indices = [P[ind] for ind in g]
        ind_set = set(indices)
        for ind in g:
            if ind in ind_set:
                cnt += 1
    print(cnt)
    


if __name__ == "__main__":
    main()

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

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

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


n,m=map(int,input().split())
A=UnionFind(n)
P=list(map(int,input().split()))
for i in range(m):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  A.union(a,b)
V=[0]*n
ans=0
AA=[]
c=0
C={}
V=[0]*n
for i in range(n):
  if A.parents[i]<0:
    AA.append([i])
    C[i]=c
    c=c+1
    V[i]=1
for i in range(n):
  if V[i]==0:
    AA[C[A.find(i)]].append(i)
for i in range(len(AA)):
    B=[]
    for j in range(len(AA[i])):
      B.append(P[AA[i][j]]-1)
    ans=ans+len(AA[i])+len(B)-len(set(AA[i])|set(B))
print(ans)

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

num = [0 for _ in range(N+1)]

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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())
    
    
uf = Unionfind(N+1)
        
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x, y)
ans = 0
for i in range(N):
    if(uf.find(i+1) == uf.find(p[i])):
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
par=[-1]*n


def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)

p=list(map(int,input().split()))
for i in range(n):
  p[i]-=1
ans=0

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

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

print(ans)

Solution (Python):
class Unionfind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)
    
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def same_check(self,x,y):
        return self.find(x) == self.find(y)

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

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

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

for _ in range(m):
    x,y = map(int,input().split())
    tree.union(x,y)
ans = 0
for i in range(n):
    if tree.find(i+1) == tree.find(p[i]):
        ans += 1
print(ans)

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


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

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

        return self.p[x]

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

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

        if u == v: return

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

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

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

uf=Uf(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]-1):
        ans+=1

print(ans)

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


def find(x):
    if par[x] < 0:
        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 False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]



par = [-1]*n

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

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

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def 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




uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)
cnt=0
for i in range(n):
    
    if uf.find(i)==uf.find(p[i]-1):
        cnt+=1

print(cnt)

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


tree=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque

groups=[]
been=[0]*n
for i in range(n):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:
                    continue
                q.append((x,y))
        groups.append(group)

ans=0
for group in groups:
    ans+= len( set(group) & set(p[g] for g in group) )

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def isSame(self, x, y):
        return self.find(x) == self.find(y)

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

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes

        
        
        self.parents = [-1] * n_nodes

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

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

        if x == y:
            return

        
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def get_size(self, x):
        return -self.parents[self.find(x)]

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

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

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    tree = UnionFind(N)
    for _ in range(M):
        x, y = map(lambda x: int(x) - 1, input().split())
        tree.unite(x, y)

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())

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

par = [i for i in range(n)]
rank = [0]*n

def UnionFind(n):
    if par[n] == n:
        return n

    parent = par[n]
    par[n] = UnionFind(parent)
    return par[n]


def Unite(left, right):
    rootLeft = UnionFind(left)
    rootRight = UnionFind(right)
    if rootLeft != rootRight:
        if rank[rootRight] < rank[rootLeft]:
            par[rootRight] = rootLeft
        else:
            par[rootLeft] = rootRight
            if rank[rootLeft] == rank[rootRight]:
                rank[rootLeft] += 1



for i in range(m):
    a, b = (i-1 for i in map(int, input().split()))
    Unite(a, b)

sum = 0
for i, p in enumerate(ps):
    sourceRoot = UnionFind(i)
    targetRoot = UnionFind(p - 1)
    if sourceRoot == targetRoot:
       sum += 1

print(sum)

Solution (Python):
n,m = map(int,input().split())

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

root = [[] for i in range(n)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

check = [-1]*n

ans = 0

for j in range(n):
    if check[j] != -1:
        continue
    stack=[j]
    check[j]=j
    while len(stack):
        v = stack.pop(0)
        for i in root[v]:
            if check[i] == -1:
                check[i]=j
                stack.append(i)
for k in range(n):
    if check[k] == check[p[k]-1] :
        ans += 1

print(ans)

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

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

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

unionfind = UnionFind(N + 1)

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

ans = 0
idx = []
for i in range(N):
    if P[i] == (i + 1):
        ans += 1
    else:
        idx.append(i)
for i in idx:
    if unionfind.same(P[i], i + 1):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  
        self.rank = [1] * n  
        self.size = [1] * 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:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

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

    def group_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.parent) if i == x]

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

    def all_group_members(self):  
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())


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

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

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

print(ans)

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]  
        self.rank = [0 for i 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.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)

    def is_root(self, x):
        return self.par[x] == x

    def roots(self):
        return [i for i in range(self.n) if self.is_root(i)]

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

    def groups(self):
        return {r: self.members(r) for r in self.roots()}


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

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