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):
n, m = list(map(int, input().split()))
pl = 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)

    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)
for i in range(m):
    a, b = list(map(int, input().split()))
    uf.union(a-1, b-1)

ans = 0
for i, p in enumerate(pl):
    if uf.same(i, p-1):
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
pl = 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)

    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)

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

ans = 0
for idx, p in enumerate(pl):
    if uf.same(idx, p-1):
        ans += 1

print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        C = [i]
        hist[i]=1
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    C.append(y)
                    hist[y]=1
        C = sorted(C)
        A.append(C)
cnt = 0
for C in A:
    B = []
    for c in C:
        B.append(P[c])
    B = sorted(B)
    cur = 0
    for i in range(len(C)):
        if cur<len(B) and C[i]==B[cur]:
            cnt += 1
            cur += 1
        elif cur<len(B) and C[i]<B[cur]:
            continue
        elif cur<len(B) and C[i]>B[cur]:
            while cur<len(B) and C[i]>B[cur]:
                cur += 1
            if cur<len(B) and B[cur]==C[i]:
                cnt += 1
            else:
                continue
print(cnt)

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 Count(self, x):
    return -self.root[self.Find_Root(x)]
uni=UnionFind(N)

for i in range(M):
    x,y=map(int, input().split())
    uni.Unite(x-1,y-1)
ans=0    
for i,p in enumerate(P):
  if uni.isSameGroup(i,p-1):
    ans+=1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():


    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]

    N, M = map(int, input().split())
    uf = UnionFind(N)  
    l=list(map(int,input().split()))

    for i in range(M):
        
        A, B = map(int, input().split())
        A,B=A-1,B-1
        uf.union(A, B)
    cnt=0
    for i in range(N):
        if uf.is_same(l[i]-1,i):
            cnt+=1
    print(cnt)

resolve()

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N, M = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))

tree = UnionFind(N)
for _ in range(M):
    fr, to = map(int, input().split())
    tree.union(fr - 1, to - 1)

ans = 0
for i, p in enumerate(P):
    ans += tree.isSameRoot(i, p)
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    P = [int(i)-1 for i in input().split()]
    XY = [[int(i)-1 for i in input().split()] for j in range(M)]

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

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for x, y in XY:
        unite(x, y)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *P,=map(int, input().split())
    P=[0]+P
    uf=UnionFindTree(N+1)
    for _ in range(M):
        x,y=map(int, input().split())
        uf.union(x,y)
    ans=0
    for i in range(1,N+1):
        if uf.same(i,P[i]): ans+=1
    print(ans)

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

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


class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

uni = UnionFind(N + 1)

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

count = 0

for index, p in enumerate(P):
    if uni.same(p, index + 1):
        count += 1

print (count)

Solution (Python):
from collections import deque


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

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

used = [False] * n
def dfs(i):
    q = deque([i])
    used[i] = True
    set_ = set([i])
    ans = 0
    while q:
        v = q.pop()
        for nxt_v in graph[v]:
            if used[nxt_v]:
                continue
            used[nxt_v] = True
            q.append(nxt_v)
            set_.add(nxt_v)
    for i in set_:
        if p[i] - 1 in set_:
            ans += 1
    return ans

res = 0
for i in range(n):
    if used[i]:
        continue
    else:
        res += dfs(i)
print(res)

Solution (Python):

import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

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

Solution (Python):
class UnionFind:

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

    def find_root(self, node):
        parent_node = self.parents[node]
        if node == parent_node:
            return node
        else:
            root_node = self.find_root(parent_node)
            self.parents[node] = root_node  
            return root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        one_rank = self.ranks[one_root]
        other_rank = self.ranks[other_root]
        if one_rank < other_rank:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if one_rank == other_rank:
                self.ranks[other_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root


def main():
    N, M = list(map(int, input().split(' ')))
    p = list(map(int, input().split(' ')))
    tree = UnionFind(N)
    for _ in range(M):
        x, y = list(map(int, input().split(' ')))
        tree.union(p[x - 1], p[y - 1])
    answer = 0
    for i in range(1, N + 1):
        if tree.is_same_group(i, p[i - 1]):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M = (int(_) for _ in input().split())
    P = [int(_) for _ in input().split()]
    swap = [[int(_) for _ in input().split()] for __ in range(M)]

    par = [i for i in range(N+1)]
    rank = [0] * (N+1)

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

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

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

    for a, b in swap:
        unite(a, b)

    ret = 0
    for i, p in enumerate(P, 1):
        if same(i, p): ret += 1
    print(ret)
    return

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        x, y = (int(x) - 1 for x in input().split())
        g[x].add(y)
        g[y].add(x)

    roots = [-1] * N
    for r in range(N):
        if ~roots[r]: continue
        dq = deque()
        dq.append(r)
        roots[r] = r
        while dq:
            v = dq.popleft()
            for u in g[v]:
                if ~roots[u]: continue
                roots[u] = r
                dq.append(u)

    cnt = sum(1 for i, pi in enumerate(p) if roots[i] == roots[pi])
    print(cnt)


if __name__ == '__main__':
    main()

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
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

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

A = UnionFind(N)

for i in range(M):
    A.union(data[i][0],data[i][1])
ans = 0
for i in range(1,N+1):
    if A.same_check(i,P[i]):
        ans += 1

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().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)

n,m=nii()
p=list(nii())

uf=UnionFind(n)

for i in range(m):
  x,y=nii()
  x-=1
  y-=1
  uf.union(x,y)

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

print(n-cnt)

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


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


def main():
    """
    <考察>
    (x, y)の組が与えられるが，親が一緒のところには自由に移動できる．
    UnionFind木で管理する．
    """
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = []
    for i in range(n):
        g.append((p[i] - 1, i))
    g.sort()  

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

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


if __name__ == '__main__':
    main()

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


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

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

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


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

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

    def size(self, A):
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        
        if (A == B):
            return False

        
        if (self.size(A) < self.size(B)):
            A, B = B, A

        
        self.parent[A] += self.parent[B]  
        self.parent[B] = A  

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  










N, M = read_ints()
P = read_ints()
uf = UnionFind(N)
for _ in range(M):
    x, y = read_ints()
    uf.unite(x - 1, y - 1)

group = defaultdict(lambda: set())
for i in range(N):
    group[uf.root(i)].add(i)

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

Solution (Python):
n,m = map(int,input().split())
p = list(map(int,input().split()))
xy = [list(map(int,input().split())) for _ in range(m)]
li = [[] for _ in range(n+1)]
for x,y in xy:
    li[x].append(y)
    li[y].append(x)
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]
        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 all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uni = UnionFind(n+1)
for i in range(n+1):
    for j in li[i]:
        uni.union(i,j)

point = 0

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

print(point)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
p = [int(i) for i in input().split()]
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)
  
for i in range(m):
  x,y = [int(i) for i in input().split()]
  unite(x-1,y-1)
  
ans = 0
for i,pi in enumerate(p):
  if pi == i+1:
    ans += 1
  else:
    if same(pi-1,i):
      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 Count(self, x):
    return -self.root[self.Find_Root(x)]
uni=UnionFind(N)
for i in range(M):
  x,y=map(int, input().split())
  uni.Unite(x,y)
  
ans=0 
for i, p in enumerate(P):
  if uni.isSameGroup(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()))
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
seen = [False]*(n+1)
ans = 0
for i in range(1, n+1):
    if seen[i] or len(graph[i])==0:
        continue
    queue = deque([i])
    seen[i] = True
    inds = {i}
    ps = {p[i-1]}
    while len(queue)>0:
        node = queue.popleft()
        for c_node in graph[node]:
            if seen[c_node]:
                continue
            seen[c_node] = True
            inds.add(c_node)
            ps.add(p[c_node-1])
            queue.append(c_node)
    ans += len(inds&ps)
for ind, i in enumerate(p):
    if seen[ind+1]:
        continue
    if ind+1==i:
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n+1)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x,y)
ans=0
for i in range(n):
  if uf.same(p[i],i+1):
    ans+=1
print(ans)

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

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            

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

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

print (ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    P = [int(i)-1 for i in input().split()]

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

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for i in range(M):
        a, b = (int(i)-1 for i in input().split())
        unite(a, b)

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


if __name__ == '__main__':
    main()