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 UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

n, m = map(int, input().split())
plist=list(map(int, input().split()))
uf = UnionFindVerSize(n)

for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x-1, y-1)
kotae=0
for i in range(n):
    if uf.is_same_group(i, plist[i]-1):
        kotae+=1
print(kotae)

Solution (Python):

import sys


class UnionFind(object):
    __slots__ = ["nodes"]

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

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x]) 
            return self.nodes[x]

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    U = UnionFind(2 * N + 1)
    for i, pi in enumerate(p):
        U.unite(i+1, N + pi)
    for xx, yy in zip(x, y):
        U.unite(xx, yy)
    res = 0
    for i in range(1, N+1):
        if U.has_same_root(i, N+i):
            res += 1
    
    print(res)
    return



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

if __name__ == '__main__':
    main()

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

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


def main():
    N, M = map(int,input().split())
    L = list(map(int,input().split()))
    UF = UnionFind(N)
    
    for i in range(M) :
        A, B = map(int,input().split())
        A -= 1
        B -= 1
        UF.union(A, B)
    
    ans = 0
    
    for i, v in enumerate(L) :
        ans += (UF.same_root(i, v-1))
    
    print(ans)
    
        

import sys
input = sys.stdin.readline

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):
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

from collections import defaultdict
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups_num(self):
        if isinstance(self.parent,list):
            return len(list(filter(lambda x: x<0, self.parent)))
        else: 
            return len(list(filter(lambda x: x<0, self.parent.values())))

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, M = inpl()
p = inpl()
xy = [None]*M
for i in range(M):
    x, y = inpl()
    xy[i] = (x-1, y-1)

uf = UnionFind(2*N)
for i in range(N):
    uf.merge(i,(p[i]-1)+N)
for x, y in xy:
    uf.merge(x,y)
ans = 0
for i in range(N):
    if uf.connected(i,i+N):
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
P = list(map(lambda x:int(x)-1,input().split()))

class UnionFind( ):
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i 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[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


uf = UnionFind(n)

for i in range(m):
    x,y = map(lambda x:int(x) - 1,input().split())
    uf.unite(x,y)
    
ans = 0 
for i in range(n):
    if uf.find(i)==uf.find(P[i]):
        ans+=1
print(ans)

Solution (Python):
from collections import deque

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

G = [[] for i in range(N)]

for i in range(len(L)) :
    u,v = L[i]
    u -= 1
    v -= 1
    
    G[u].append(v)
    G[v].append(u)

explored = [0 for i in range(N)]

ans = 0

for i in range(N) :
    
    if explored[i] :
        continue
    
    explored[i] = 1
    q = deque([i])
    
    A = []
    B = []
    while q :
        now = q.popleft()
        
        A.append(now)
        B.append(P[now]-1)
        
        for to in G[now] :
            if explored[to] :
                continue
            
            q.append(to)
            explored[to] = 1
    
    C = set(A) & set(B)
    ans += len(C)
    

print(ans)

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

sys.setrecursionlimit(10 ** 7)

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

uf = UnionFind(n)
for _ in range(m):
    x, y = li_()
    uf.unite(x, y)

for i in range(n):
    uf.find(i)

ans = 0
for i, pi in enumerate(p):
    if uf.isSame(i, pi):
        ans += 1

print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x
        
        self.par[y] = x
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def __repr__(self):
        return ', '.join(str(x) for x in self.par)

t = UnionFind(N)
for x, y in X:
    t.unite(x - 1, y - 1)
    
cnt = 0
for i in range(N):
    cnt += int(t.same(i, p[i] - 1))
print(cnt)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[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.size[self.root(x)]


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

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

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

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[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.size[self.root(x)]


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

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

ans = 0
for i in range(n):
    if uf.issame(i,p[i]):
        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 i in range(M)]
class UnionFind:
    def __init__(self,N,P):
        self.Parent=[-1]*N
        self.num=[{p-1:1} for p in P]
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            self.num[rm].update(self.num[rn])
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N,P)
for xy in XY:
    u.unite(xy[0]-1,xy[1]-1)
ans=0
for n in range(N):
    if n in u.num[u.root(n)]:
        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.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 size(self, x):
        return -self.root[self.find_root(x)]


UF = UnionFind(N)
for i 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):
N,M = list(map(int,input().split()))

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

e_list = [[] for i in range(N)]

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

from collections import deque

def BFS(vi,color,color_list,e_list):
    Q = deque([vi])
    color_list[vi]=color
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=color
                Q.appendleft(v1)
    return color_list

color_list = [-1 for i in range(N)]
color = 0
for i in range(N):
    if color_list[i]==-1:
        color_list = BFS(i,color,color_list,e_list)
        color+=1
count=0

for i in range(N):
    if color_list[p[i]-1]==color_list[i]:
        count+=1

print(count)

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

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)

N, M = map(int, input().split())
L = [int(v) - 1 for v in input().split()]

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

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: 
            return v
        else:
            
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
        else: 
            self.vertices[s2] += self.vertices[s1] 
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

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.union(x-1, y-1)
ans = 0
for i in range(N):
    if uf.is_connected(i, P[i]-1):
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
P=[int(i) for i in input().split()]
PP=[0]*n
for i in range(n):
  PP[P[i]-1]=i+1
par=[-1]*n

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

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,PP[i]-1):
    ans+=1
print(ans)

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

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

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

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

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

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

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

Solution (Python):
N, M = map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]

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

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

Solution (Python):
n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [list() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].append(y)
  d[y].append(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()


N,M = na()
p = na()

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)]
tr = UnionFind(N)
for i in range(M):
    q1,q2 = na()
    tr.Unite(q1,q2)
ans =0
for i in range(N):
    
    tmp = p[p[i]-1]
    if(tr.isSameGroup(p[i],tmp)):
        ans+=1

print(ans)

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def solve():
    
    N,M = map(int,input().split())
    
    P = list(map(int,input().split()))
    XY = []
    U = UnionFind(N+1)

    for x,y in [list(map(int,input().split())) for _ in range(M)]:
        U.Unite(x,y)

    ans = 0
    for e,p in enumerate(P,1):
        if U.isSameGroup(e,p):
            ans += 1
    print(ans)

    


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict
N,M=map(int,raw_input().split())
P=map(int,raw_input().split())
X=[];Y=[]
for i in range(M):
    x,y=map(int,raw_input().split())
    X.append(x);Y.append(y)


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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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

uf=UnionFind(N+1)
for x,y in zip(X,Y):
    uf.union(x,y)
groups=defaultdict(set)
for n in range(1,N+1):
    groups[uf.find(n)].add(n)
ans=N
for _,A in groups.iteritems():
    B=set()
    for a in A:
        B.add(P[a-1])
    ans-=len(A-B)
print(ans)

Solution (Python):
class UNION_FIND(object):
    def __init__(self,n):
        
        
        
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  
            return self.parent[x]
 
    def size(self,x):
        
        return -self.parent[self.root(x)]   
        
    def union(self,x,y):
        
        
        
        x=self.root(x)
        y=self.root(y)
        
        if x==y:   
            return False
            
        
        
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True


a,b=map(int,input().split())
*p,=map(int,input().split())
u=UNION_FIND(a)

for i in range(b):
    x,y=map(int,input().split())
    u.union(x-1,y-1)
ans=0
for i in range(a):
    ans+=(u.root(i)==u.root(p[i]-1))
print(ans)

Solution (Python):
from numpy import*
from collections import*
class UNION_FIND(object):
    def __init__(self,n):
        
        
        
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  
            return self.parent[x]
 
    def size(self,x):
        
        return -self.parent[self.root(x)]   
        
    def union(self,x,y):
        
        
        
        x=self.root(x)
        y=self.root(y)
        
        if x==y:   
            return False
            
        
        
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  
        self.parent[y]=x   
        return True


a,b=map(int,input().split())
*p,=map(int,input().split())
u=UNION_FIND(a)
d=defaultdict(list)

p=array(p)
for i in range(b):
    x,y=map(int,input().split())
    u.union(x-1,y-1)
for k,v in enumerate(u.root(i)for i in range(a)):
    d[v].append(k)
ans=0
for i in d.values():
    i=array(i)
    ans+=len(set(i+1)&set(p[i]))
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

    def 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 p[i]-1 == i or uf.same(i,p[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)]

UF = list(range(n+1))

def search(uf,i):
    if uf[i] == i:
        return i
    else:
        uf[i] = uf[search(uf,uf[i])]
        return uf[i]

for x,y in XY:
    i = search(UF,x)
    j = search(UF,y)
    UF[x] = min(x,y,i,j)
    UF[y] = UF[x]
    UF[i] = UF[x]
    UF[j] = UF[x]
for i in range(1,n+1):
    UF[i] = search(UF,i)
ans = 0
for p,j in zip(P,range(1,n+1)):
    if p == j:
        ans += 1
    elif UF[p] == UF[j]:
        ans += 1
print(ans)