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

if __name__ == '__main__':
    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)
    res = 0
    for i in range(n):
        if uf.same(i,p[i]-1):
            res += 1
    print(res)

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

def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def connected(u, v):
    return 1 if root(u) == root(v) else 0

N, M = map(int, input().split())
P = list(map(int, input().split()))
par = [i for i in range(N)]
rank = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)
res = 0
for i in range(N):
    res += connected(i, P[i]-1)
print(res)

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

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

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

    uf = UnionFind(N)
    for i in range(M):
        x,y = map(int, input().split())
        uf.union(x-1,y-1)
        
    cnt = 0
    for i,p in enumerate(p_list):
        cnt += 1 if uf.same(p-1, i) else 0
    print(cnt)

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n, m = None, read = 0):
        self.n = n
        self.parents = [-1] * n
        if read:
            if m is None:
                exit(print("Warning: What is M"))
            for i in range(m):
                a, b = map(int, input().split())
                self.union(a - 1, b - 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()}

n, m = map(int, input().split())
*p, = map(int, input().split())
UF = UnionFind(n, m, read = 1)

a = 0
for i in range(n):
    P = p[i] - 1
    if UF.same(P, i):
        a += 1
print(a)

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=list(map(int,input().split()))
uf=UnionFind(N+1)
p=list(map(int,input().split()))
for i in range(M):
    x,y=list(map(int,input().split()))
    uf.union(x,y)
count=0
for i in range(1,N+1):
    if (uf.same(p[i-1],i)):count+=1
print(count)

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)
for i in range(m):
  x,y = map(int, input().split())
  uf.union(x-1,y-1)
  
count = 0
for i in range(n):
  if uf.same(p[i]-1, i):
    count += 1
    
print(count)

Solution (Python):

import sys

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

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

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=list(map(int,input().split()))
p=list(map(int,input().split()))

tree=UnionFind(N+1)

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

    tree.union(p[x-1],p[y-1])
ans=0

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

print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self.par = [-1] * N

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

  def union(self, x,y):
    p1,p2 = self.find(x), self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

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

N,M = map(int,input().split())
A = list(map(int,input().split()))
uf = UF(N+1)
for _ in range(M):
  u,v = map(int,input().split())
  uf.union(u,v)

res = 0
for i in range(N):
  if i+1 == A[i] or uf.same(i+1, A[i]):
    res += 1

print(res)

Solution (Python):



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

    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 find(self, x):          
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

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

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

    ret = 0
    for i in range(N):
        if uf.same(P[i]-1, i):
            ret += 1
    print(ret)

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 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)
count = 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):
        count += 1

print(count)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
P = nl()
assert len(P) == N
pairs = []
for i in range(M):
    x, y = nm()
    x -= 1
    y -= 1
    pairs.append((x, y))


def solve():
    uf = UnionFind(N)
    for (x, y) in pairs:
        uf.union(x, y)
    cnt = 0
    for i in range(N):
        if uf.same(P[i] - 1, i):
            cnt += 1
    return cnt


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


if __name__ == "__main__":
    print(solve())

Solution (Python):
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

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

  def same(self, n1, n2):
    return self.find(n1) == self.find(n2)

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




for x,y in xy:
  uf.union(x,y)

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

print(res)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
p = [0] + list(map(int,input().split()))
l = [[] for _ in range(N+1)]
for i in range(M):
  x,y = map(int,input().split())
  l[x].append(y)
  l[y].append(x)


lp = [i for i in range(N+1)] 

def root(x):
  if lp[x] == x:
    return x
  else:
    lp[x] = root(lp[x])
    return lp[x]

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

def unite(x,y):
  x = root(x)
  y = root(y)
  if x != y:
    lp[x] = y 

seen = [False]*(N+1)
for i in range(1,N+1):
  if seen[i] == False:
    seen[i] = True
    d = deque([i])
    while len(d)>0:
      v = d.popleft()
      for j in l[v]:
        if seen[j] == False:
          seen[j] = True
          unite(j,i)
          d.append(j)

cnt = 0
for i in range(1,N+1):
  cnt += int(det(p[i],i))
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
P = list(map(int, input().split()))


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)


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

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

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

par = {x:x for x in range(1, n+1)}

def root(node):
    if par[node] == node:
        return node
    par[node] = root(par[node])
    return par[node]

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(pow(10,9))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.find(self.root[x])
    def union(self,x,y):
        x,y = self.find(x),self.find(y)
        if x == y:return
        if self.rank[x]<self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.root[y] = x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(200000)

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

count = 0
for i in range(N):
    if tree.find(i+1) == tree.find(P[i]):
        count += 1

print(count)

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

n, m = map(int, input().split())
p = list(map(lambda x: int(x)-1, input().split()))
from collections import defaultdict
es = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    es[u-1].add(v-1)
    es[v-1].add(u-1)
    
count = 0
seen = [False] * n
for u in range(n):
    index = set()
    values = set()
    if seen[u]:
        continue
    index.add(u)
    values.add(p[u])
    q = [u]
    seen[u] = True
    while q:
        u = q.pop()
        for v in es[u]:
            if not seen[v]:
                q.append(v)
                seen[v] = True
                index.add(v)
                values.add(p[v])
    count += len(index & values)
print(count)

Solution (Python):
import numpy as np
n,m = map(int,input().split())
lis = list(map(int,input().split()))
path = [[] for i in range(n)]

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

gone = np.array([-1] * n)
numberindex = set()
realnumber = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber.add(lis[a]-1)
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        ans += len(realnumber & numberindex)
        realnumber,numberindex = set(),set()
print(ans)

Solution (Python):
from collections import defaultdict

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


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

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

z = []
for i in range(M):
  t, s = map(int,input().split())
  z.append((t,s))

uf = UnionFind(N)

for i in range(M):
  uf.union(z[i][0]-1, z[i][1]-1) 


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

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

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

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = map(int,input().split())
tree = UnionFind(N)
P = list(map(int,input().split()))
for _ in range(M):
    x,y = map(int,input().split())
    tree.union(x,y)

indeces = {}
indeces2 = {}
for i in range(N):
    indeces[P[i]]=i+1
    indeces2[i+1]=P[i]

group = {}
group2 = {}
for i in range(1,N+1):
    r = tree.find(i)
    if r not in group:
        group[r]=set()
    group[r].add(i)
    group2[i]=r

ans = 0
for n,index in indeces.items():
    if n == index:
        ans += 1
    else:
        groupNum = group2[index]
        if n in group[groupNum]:
            ans += 1
            a = indeces2[n] 
            indeces2[n] = n
            indeces2[index] = a
            indeces[a] = index
            indeces[n] = n

print(ans)

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

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

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = map(int,input().split())
P = list(map(int,input().split()))
dic = {}
dic2 = {}
for i in range(1,N+1):
    dic[P[i-1]]=i
    dic2[i]=P[i-1]

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

indexGroup = {}
for i in range(1,N+1):
    root = tree.find(i)
    if root not in indexGroup:
        indexGroup[root]=set()
    indexGroup[root].add(i)

for p,i in dic.items():
    root = tree.find(i)
    if p in indexGroup[root]:
        n = dic2[p]
        dic[p] = p
        dic2[p] = p
        dic[n] = i
        dic2[i] = n

count = 0
for p,i in dic.items():
    if p==i:
        count += 1
print(count)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
p = [0] + LI()

g = [i for i in range(N+1)]
g_num = [1 for _ in range(N+1)]

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

def union(x,y):
    if find(x) == find(y): return
    if g_num[g[x]] < g_num[g[y]]: x,y = y,x
    g_num[g[x]] += g_num[g[y]]
    g[g[y]] = g[x]

for _ in range(M):
    x,y = LI()
    union(x,y)

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

Solution (Python):
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)
    
N,M=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

p=list(map(lambda x:int(x)-1,input().split()))
dic={p[i]:i for i in range(N)}

for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    union(dic[x],dic[y])
cnt=0
for i in range(N):
    if same(i,p[i]):
        cnt+=1
print(cnt)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.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 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()}
n,m = inpl()
a = inpl()
uf = UnionFind(n)
for i in range(m):
    x,y = inpl()
    x -= 1; y -= 1
    uf.union(x,y)
res = 0
for i in range(n):
    if uf.same(a[i]-1, i):
        res += 1
print(res)