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.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
arr=list(map(int,input().split()))
t=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  t.Unite(a,b)
ans=0
for i in range(n):
  if arr[i]==(i+1):
    ans+=1
  else:
    if t.isSameGroup((i+1),arr[i]):
      ans+=1
print(ans)

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

P = [int(x) - 1 for x in input().split()]

pear = []
for i in range(M):
	pear.append([int(x) - 1 for x in input().split()])


par = []
for i in range(N):
	par.append(i)

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

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

def unite(x, y):
	X = root(x)
	Y = root(y)
	if X != Y:
		par[X] = Y

for i in range(M):
	unite(pear[i][0], pear[i][1])

ans = 0

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

print(ans)

Solution (Python):

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

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    x-=1
    y-=1
    U.merge(x,y)
print(sum(U.is_united(i,p-1) for i,p in enumerate(P)))

Solution (Python):
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

def get_Parent(n):
    if Parent[n] == -1:return n
    par = get_Parent(Parent[n])
    Parent[n] = par
    return par
def merge(x,y):
    x = get_Parent(x)
    y = get_Parent(y)
    if x!=y: Parent[y] = x
    return
def is_united(x,y):
    return get_Parent(x)==get_Parent(y)

Parent = [-1]*N
for x,y in XY:
    x-=1
    y-=1
    merge(x,y)
print(sum(is_united(i,p-1) for i,p in enumerate(P)))

Solution (Python):
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for x,y in XY:
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
def connect_bfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

done = [False]*N
ans = 0
for i in range(N):
    if done[i]:continue
    J = connect_bfs(N,E,i)
    PJ = set(P[j]-1 for j in J)
    ans += len(J & PJ)
    for j in J:
        done[j] = True
print(ans)

Solution (Python):
def solve(p, query):
    ans = 0
    for a, b in query:
        unite(a, b)

    for pi in p:
        if is_same(pi, p[pi]):
            ans += 1

    return ans


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


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


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


if __name__ == '__main__':
    n, m = map(int, input().split())
    query = []
    par, rnk = [0]*n, [0]*n
    p = list(map(int, input().split()))
    p = list(map(lambda x: x-1, p))

    for _ in range(m):
        a, b = map(int, input().split())
        query.append((a-1, b-1))

    for i in range(n):
        par[i] = i

    print(solve(p, query))

Solution (Python):
class union_find:

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        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

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

        self.par[x] += self.par[y]
        self.par[y] = x
        return

    def sizeof(self, x):
        return -par[root(x)]

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

uf = union_find(n)

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

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

print(cnt)

Solution (Python):
N, M = map(int, input().split())
P = list(map(lambda v: int(v) - 1, input().split()))
grp = []
for i in range(0, N):
	grp.append(i)
for i in range(0, M):
	X, Y = map(lambda v: int(v) - 1, input().split())
	rootX = X
	que1 = []
	while True:
		if grp[rootX] == rootX:
			break
		que1.append(rootX)
		rootX = grp[rootX]
	for j in range(0, len(que1)):
		grp[que1.pop(0)] = rootX
	rootY = Y
	que2 = []
	while True:
		if grp[rootY] == rootY:
			break
		que2.append(rootY)
		rootY = grp[rootY]
	for j in range(0, len(que2)):
		grp[que2.pop(0)] = rootY
	grp[rootX] = rootY
cnt = 0
for i in range(0, N):
	root1 = i
	que1 = []
	while True:
		if grp[root1] == root1:
			break
		que1.append(root1)
		root1 = grp[root1]
	for j in range(0, len(que1)):
		grp[que1.pop(0)] = root1
	root2 = P[i]
	que2 = []
	while True:
		if grp[root2] == root2:
			break
		que2.append(root2)
		root2 = grp[root2]
	for j in range(0, len(que2)):
		grp[que2.pop(0)] = root2
	if root1 == root2:
		cnt += 1
print(cnt)

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



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



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

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

def union(x,y):
    x = root(x)
    y = root(y)
    
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    
    if not same(x-1,y-1):
        union(x-1,y-1)

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

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

N,M = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
un = UnionFind(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    un.unite(x-1,y-1)
cnt = 0
for ind,i in enumerate(p):
    if(un.same(ind,i-1)):
        cnt+=1
print(cnt)

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

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


n, m = MI()
p = LI()
pair = [LI() for _ in range(m)]
uf = UnionFind(n)
for x, y in pair:
    uf.unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if uf.same(p[i] - 1, 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 _ in [0]*M]
z=[[i,1] for i in range(N)]

def root_find(a):
    while(a!=z[a][0]):
        a=z[a][0]
    return a

def union(a,b):
    ra=root_find(a[0])
    rb=root_find(b[0])
    if z[ra][1]<=z[rb][1]:
        z[ra][0]=rb
        z[rb][1]=max(z[rb][1],z[ra][1]+1)
    else:
        z[rb][0]=ra
        z[ra][1]=max(z[ra][1],z[rb][1]+1)
    
for i in range(M):
    union(z[xy[i][0]],z[xy[i][1]])

for i in range(N):
    z[i][0]=root_find(z[i][0])

dic=dict()

for i in range(N):
    zz=z[i][0]
    if zz not in dic.keys():
        dic[zz]=[i]
    else:
        dic[zz].append(i)

list1=list(dic.values())
list2=[[p[a] for a in list1[i]] for i in range(len(list1))]

cnt=sum(len(set(list1[i])&set(list2[i])) for i in range(len(list1)))
print(cnt)

Solution (Python):
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            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)
        self.par[x] = y

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


n, m = map(int, input().split())
p = list(map(int, input().split()))
p = [v-1 for v in p]

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

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

print(ans)

Solution (Python):
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            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)
        self.par[x] = y

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

n, m = map(int, input().split())
p = list(map(int, input().split()))
p = [v-1 for v in p]

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

a = defaultdict(list)
b = defaultdict(list)
for i in range(n):
    k = uf.find(i)
    a[k].append(i)
    b[k].append(p[i])

ans = 0
for k in a.keys():
    ans += len(set(a[k]) & set(b[k]))

print(ans)

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

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
N,M = map(int,input().split())
u = UnionFind(N)
p = list(map(int,input().split()))
for _ in range(M):
    x,y = map(int,input().split())
    u.union(p[x-1]-1,p[y-1]-1)

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

print(ans)

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

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        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 group_num(self):
        return self.grp


n,m=map(int, input().split())
p=[int(i) for i in input().split()]
uf=UnionFind(n+1)

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

ans=chk=0
for a,i in enumerate(p):
    if uf.same(p[a],a+1): ans+=1
print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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 size(self, x):
    return self._size[self.find_root(x)]

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

  def groupnum(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())
UF=UF(n)
p=list(map(int,input().split()))
for i in range(m):
  x,y=map(int,input().split())
  UF.unite(x-1,y-1)

ct=0
for i in range(n):
  if UF.find_root(i)==UF.find_root(p[i]-1):ct+=1
print(ct)

Solution (Python):


def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind =  data[i]
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

print(ans)

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

parent = [i for i in range(n)]
height = [1 for _ in range(n)]

def root(i):
  if parent[i] != i:
    parent[i] = root(parent[i])
  return parent[i]

def union(i, j):
  pi = root(i)
  pj = root(j)
  if pi == pj:
    return
  else:
    if height[pi] < height[pj]:
      parent[pi] = pj
    elif height[pi] > height[pj]:
      parent[pj] = pi
    else:
      if pi < pj:
        parent[pj] = pi
        height[pi] += 1
      else:
        parent[pi] = pj
        height[pj] += 1

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

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

print(ans)

Solution (Python):

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)

group = [0]*(N+1)
ans = 0
for i,num in enumerate(P,1):
    ex_space = [i]
    for ex_point in ex_space:
        if group[ex_point]:
            continue
        group[ex_point] = i
        ex_space.extend(graph[ex_point])
    ans += (group[num] == group[i])
 
print(ans)

Solution (Python):
import sys
from copy import copy

sys.setrecursionlimit(10**5)


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


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


def unite(x, y, S):
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [N, M] = [int(i) for i in input().split()]

    S = [int(i) for i in range(N+1)]
    p = [0] + [int(num) for num in input().split()]

    for i in range(M):
        [x, y] = [int(i) for i in input().split()]
        unite(x, y, S)

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

Solution (Python):
N,M = [int(s) for s in input().split()]
p = [0] + [int(s) for s in input().split()]
par = []
counter = 0

for i in range(N+1):
    par.append(i)
    
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

for i in range(M):
    x,y = [int(s) for s in input().split()]
    union(x,y)
    
for i in range(1,N+1):
    if same(i,p[i]):
        counter += 1

print(counter)

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in read(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


def main():
    N, M = readi(2)
    ips = {ip[1]: ip for ip in enumerate(readi(N), 1)}
    uf = UnionFind(ips.values())
    for _ in range(M):
        x, y = readi(2)
        uf.unite(ips[x], ips[y])

    ans = 0
    for g in uf.grouper():
        iss, ps = zip(*g)
        ans += len(iss) - len(set(iss) - set(ps))

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
def init(n):
    return list(range(n+1))
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N, M = map(int, input().split())
union_find_lis = init(N)
P = [0] + [int(s) for s in input().split()]
for _ in range(M):
    x, y = map(int, input().split())
    union(union_find_lis, x, y)
count = 0
for index in range(1, N+1):
    if sameset(union_find_lis, P[index], index):
        count += 1
print(count)

Solution (Python):

def init(n):
    lis = []
    for i in range(n+1):
        lis.append(i)
    return lis
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N, M = map(int, input().split())
input_lis = [0]+[int(p) for p in input().split()]
union_find_lis = init(N)
for _ in range(M):
    x, y = map(int, input().split())
    union(union_find_lis, x, y)
count = 0
init_flag = True
for index, num in enumerate(input_lis):
    if init_flag:
        init_flag = False
    else:
        if sameset(union_find_lis, index, num):
            count += 1
print(count)

Solution (Python):


class Tree():
    def __init__(self, array):
        n = len(array)
        
        self.roots = [x for x in range(n + 1)]

    def get_root(self, a):
        if self.roots[a] == a:
            return a
        else:
            self.roots[a] = self.get_root(self.roots[a])
            return self.roots[a]

    def unite(self, x, y):
        if self.get_root(x) == self.get_root(y):
            pass
        else:
            self.roots[self.get_root(y)] = self.get_root(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    p_array = [int(x) for x in input().split()]
    xy_array = [[int(x) for x in input().split()] for y in range(m)]

    tree = Tree(p_array)

    
    for x, y in xy_array:
        tree.unite(x, y)

    res = 0
    for i in range(1, n + 1):
        if tree.get_root(i) == tree.get_root(p_array[i-1]):
            res += 1
    print(res)

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

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

    def 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 = list(map(int, input().split()))
tree = UnionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    tree.union(x, y)
ans = 0
for i, pi in enumerate(p):
    if tree.check(i + 1, pi):
        ans += 1
print(ans)

Solution (Python):

















import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50





class UnionFind(object):
 
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[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]:
            x, y = y, x
 
        self.size[x] += self.size[y]
        self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count(self, x):
        return self.size[self.find(x)]

N, M = l_inpl()
p = l_inpl()

uf = UnionFind(N)
for _ in range(M):
    xi, yi = l_inpl()
    xi, yi = xi-1, yi-1
    uf.union(xi, yi)

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

print(ans)

Solution (Python):

import sys


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: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uni = UnionFind(N)
    for xx,yy in zip(x,y):
        uni.Unite(xx-1,yy-1)  

    cnt = 0
    for i,pp in enumerate(p):
        if  i+1 == pp or uni.isSameGroup(i,pp-1):
            cnt += True

    print(cnt)

    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):
n,m=map(int,input().split())
p=[int(i) for i in input().split()]
l=[0 for i in range(n)]
for i in range(n):
    l[p[i]-1]=i
xy=[]

par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(m):
    a=[int(j)-1 for j in input().split()]
    xy.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

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