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



import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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
n,m = LI()
p = LI()
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for _ in range(m):
    x,y = LI()
    if root(x-1) != root(y-1):
        union(x-1,y-1)

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

Solution (Python):



import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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
n,m = LI()
p = LI()
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for _ in range(m):
    x,y = LI()
    if root(x-1) != root(y-1):
        union(x-1,y-1)

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

Solution (Python):
from collections import defaultdict

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

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

es = []

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for a,b in es:
    uf.unite(a,b)


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

Solution (Python):

def wantp(n):

    Q = []

    while True:

        if lis[n] == n:
            ans = n
            break

        else:
            Q.append(n)
            n = lis[n]

    for i in Q:
        lis[i] = ans

    return ans



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

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


lis = [0] * (2 * N + 1)

rank = [0] * (2 * N + 1)

for i in range(2 * N + 1):

    i -= N

    lis[i] = i

for i in range(N):

    lis[-p[i]] = i + 1
    rank[i + 1] = 1

for i in range(M):

    x,y = map(int,input().split())

    if x > M and y > M:
        continue;

    xp = wantp(x)
    yp = wantp(y)

    if rank[xp] > rank[yp]:

        lis[yp] = lis[xp]

    elif rank[xp] < rank[yp]:

        lis[xp] = lis[yp]

    else:

        lis[yp] = lis[xp]
        rank[xp] += 1

answer = 0

for i in range(N):

    i += 1
    if wantp(i) == wantp(-i):
        answer += 1

print (answer)

Solution (Python):
N, M = map(int, input().split())
ps = list(map(int, input().split()))
G = list(range(N))
def getparent(n):
  if G[n] == n:
    return n
  G[n] = getparent(G[n])
  return G[n]
for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  x = getparent(x)
  y = getparent(y)
  G[x] = y

Ss = [set() for i in range(N)]
for i in range(N):
  j = getparent(i)
  Ss[j].add(ps[i])

r = 0
for i in range(N):
  if i+1 in Ss[G[i]]:
    r += 1
print(r)

Solution (Python):

import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):  
        self.parent = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

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

    def is_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
        
        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 main():
    
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    U = UnionFind(N)  
    for v, u in E:  
        U.unite(v, u)
    ans = sum(U.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    group[v] = color  
    for u in G[v]:  
        if not group[u]:  
            dfs(u, color)


def main():
    
    global G, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    group = [0] * (N + 1)
    color = 1
    for v in range(1, N + 1):  
        if not group[v]:
            dfs(v, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    seen[v] = 1  
    group[v] = color
    for u in G[v]:  
        if not seen[u]:  
            dfs(u, color)


def main():
    
    global G, seen, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    seen, group = [0] * (N + 1), [0] * (N + 1)
    color = 1
    for i in range(1, N + 1):  
        if not seen[i]:
            dfs(i, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys,math,itertools,bisect,copy,re

from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

input = sys.stdin.readline

INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
sys.setrecursionlimit(1000000)








N,M = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]




PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

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



D1 = dict()
D2 = dict()

for i in range(N):
    grp = root(i)
    s1 = D1.get(grp, set())
    s1.add(i+1)
    D1[grp] = s1

    s2 = D2.get(grp, set())
    s2.add(P[i])
    D2[grp] = s2




ans = 0
for grp in set(PARENT):
    s1 = D1.get(grp, set())
    s2 = D2.get(grp, set())
    ans += len(s1 & s2)

print(ans)

Solution (Python):
n, m = map(int, input().split())
pp = list(map(int, input().split()))
xyxy = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

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

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

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

uf = UnionFind(n)
for x, y in xyxy :
    uf.union(x-1, y-1)
for i in range(n) :
    uf.find(i)

d = {}
for i, k in enumerate(uf) :
    if k not in d :
        d[k] = {i}
    else :
        d[k].add(i)

e = {}
for k, set0 in d.items():
    e[k] = set()
    for i in set0 :
        e[k].add(pp[i]-1)

ans = 0
for k in d.keys() :
    set0 = d[k]
    set1 = e[k]
    ans += len(set0&set1)

print(ans)

Solution (Python):

class UnionFind():

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

    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 False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]


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

Uni = UnionFind(N)


for _ in range(M):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    
    Uni.Unite(x, y)

a = [set() for _ in range(N)]
for i in range(N):
    
    r = Uni.FindRoot(i)
    
    a[r].add(i)

ans = 0
for i in range(N):
    for j in a[i]:
        if p[j] - 1 in a[i]:
            ans += 1
print(ans)

Solution (Python):

class UnionFind():

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

    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 False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]


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

Uni = UnionFind(N)


for _ in range(M):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    
    Uni.Unite(x, y)

a = [set() for _ in range(N)]
for i in range(N):
    
    r = Uni.FindRoot(i)
    
    a[r].add(i)
    
ans = 0
for i in range(N):
    for j in a[i]:
        if p[j] - 1 in a[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 range(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=list(map(int,input().split()))
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
ans=0
for i in range(n):
    if uf.same_check(i+1,p[i]):ans+=1
print(ans)

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


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 x, y in XY:
    uni.Unite(x, y)

group = {}
for i, r in enumerate(uni.root):
    if r < 0:
        group[i] = set([i])
for i, r in enumerate(uni.root):
    if r > 0:
        w = uni.Find_Root(i)
        group[w].add(i)

ans = 0
for k, v in group.items():
    if k == 0:
        continue
    L = set()
    for ind in v:
        L.add(P[ind-1])
    ans += len(v & L)
print(ans)

Solution (Python):

import sys, math, fractions, itertools

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

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


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.unite(x[i]-1, y[i]-1)
    counter = 0
    for i in range(N):
        if uf.is_same_group(i, p[i]-1):
            counter += 1
    print(counter)
    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(x) for x in input().split()]

XY = [0]*M
for i in range(M):
    X, Y = [int(x) for x in input().split()]
    XY[i] = X, Y



parent = [x for x in range(N+1)]

def union(x, y):
    px = find(x)
    py = find(y)
    if px != py:
        parent[py] = px
    
    
    

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]
        
for x, y in XY:
    union(x, y)

cnt = 0
if False:
    print("P     ", " ".join(str(x) for x in P))
    print("parent", " ".join(str(x) for x in parent[1:]))
    print("same  ", " ".join("*" if find(i+1) == find(p) else " " for i, p in enumerate(P)))
for i, p in enumerate(P):
    if find(i+1) == find(p):
        cnt += 1
print(cnt)

Solution (Python):
def find(x):
    while union[x] != x:
        x = union[x]
        
    return x

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

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

for i in range(M):
    x, y = map(int, input().split())
    x = find(x)
    while union[y] != y:
        union[y], y = x, union[y]
        
    union[y] = x
    
ans = 0
for idx, n in enumerate(p):
    if idx+1 == n:
        ans += 1
    else:
        x, y = find(idx+1), find(n)
        if x == y:
            ans += 1
        
print(ans)

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

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

uni = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if uni.same(x, y):
        pass
    else:
        uni.connect(x, y)

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

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

UF=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    UF.Unite(x,y)
ans=0
for i in range(n):
    if UF.isSameGroup(i+1,p[i]):
        ans+=1
print(ans)

Solution (Python):
class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

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

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

        
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

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

    def has_same_parent(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 + 1)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)

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

Solution (Python):

"""
方針
ペアになっているものは、順序が任意になるという認識
-> UnionFindで行ける
"""

class UnionFind:
    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
        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)
        self.par[x] = y
    
    
    def judge(self,x,y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n)

for i in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    if not uf.judge(x,y):
        uf.union(x,y)
ans = 0
for i,p in enumerate(ps):
    if uf.find(p-1) == uf.find(i):
        ans += 1
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)
        
    def Find_root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        x = self.Find_root(x)
        y = self.Find_root(y)
        if (x == y):
            return
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_root(x) == self.Find_root(y)
    
    def Count(self, x):
        return - self.root[self.Find_root(x)]
    
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
union = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    union.Unite(x - 1, y - 1)
count = 0
for i, pp in enumerate(p):
    if union.Find_root(i) == union.Find_root(pp - 1):
        count += 1
print(count)

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

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

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

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

n,m=map(int,input().split())
p=list(map(int,input().split()))
l=[list(map(int,input().split())) for _ in range(m)]
UF=UnionFind(n)
for i in l:
    UF.Unite(i[0],i[1])
ans=0
for i in range(n):
    if UF.isSameGroup(i+1,p[i]):ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0]*(n+1)

    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)


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, y)

ans = 0
for n in range(N):
    if uf.are_same(P[n], n+1):
        ans += 1

print(ans)

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

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

node_list = [UnionFindNode(i) for i in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    node_list[x-1].unite(node_list[y-1])

ans = 0
for i, p in enumerate(p_array):
    if node_list[i].find() == node_list[p-1].find() or i == p-1:
        ans += 1

print(ans)

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

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


N, M = map(int, input().split())
p = [int(s) - 1 for s in input().split()]
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)
ans = [uf.connected(i, v) for i, v in enumerate(p)].count(True)
print(ans)

Solution (Python):
n,m=map(int,input().split());p=list(map(int,input().split()));z=0;import sys;sys.setrecursionlimit(10**9);f=[i for i in range(n)]
def r(f,x):
  if f[x]!=x:f[x]=r(f,f[x])
  return f[x]
def u(f,a,b):
  x,y=r(f,a),r(f,b)
  if x!=y:f[x]=y
for i in range(m):a,b=map(int,input().split());u(f,a-1,b-1)
for i in range(n):z+=r(f,i)==r(f,p[i]-1)
print(z)

Solution (Python):
n,m=map(int,input().split())
p=list(map(int,input().split()))
ans=0
import sys;sys.setrecursionlimit(10**9)
class u():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(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;self.r[y]+=self.r[x]==self.r[y]
u=u(n)
for i in range(m):
  a,b=map(int,input().split())
  u.u(a-1,b-1)
for i in range(n):
  if p[i]==i+1:ans+=1
  elif u.f(i)==u.f(p[i]-1):ans+=1
print(ans)