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. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Accepted

Solution code:
class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]

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

    def unite(self,x,y):
        rx = self.root(x)
        ry = self.root(y)
        if rx!=ry:
            self.par[max(rx,ry)] = min(rx,ry)
            
    def same(self,x,y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return True
        else:
            return False


def main():
    n,m = map(int,input().split())
    p = [int(i) for i in input().split()]
    ans = 0
    uf = unionfind(n)
    for i in range(m):
        x,y  = map(int,input().split())
        uf.unite(x,y)
        
    for i in range(1,n+1):
        uf.root(i)
        
    for i in range(n):
        if p[i] == i+1:#ループのindexと頂点ナンバーに1の差があるから
            ans += 1
        else:
            if uf.same(p[i],p[p[i]-1])==True:
                ans += 1
            else:
                continue
    print(ans)
main()

Submission status: Accepted

Solution code:
class UnionFind:
	"""
	class UnionFind
	https://note.nkmk.me/python-union-find/
	
	order O(log(n))
	
	n = the number of elements
	parents = the list that contains "parents" of x. be careful that it doesn't contain "root" of x.
	"""
	def __init__(self, n):
		"""
		make UnionFind
		:param n: the number of elements
		"""
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		"""
		:param x: an element
		:return: the root containing 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):
		"""
		:param x, y: an element
		"""
		# root
		x = self.find(x)
		y = self.find(y)
		if x == y:
			# already same group so do nothing
			return
		if self.parents[x] > self.parents[y]:
			# the root should be min of group
			x, y = y, x
		# remind that x, y is the root, x < y, then, y unions to x.
		self.parents[x] += self.parents[y]
		# and then y's parent is x.
		self.parents[y] = x
	def size(self, x):
		# return the size of group
		return -self.parents[self.find(x)]
	
	def same(self, x, y):
		# return whether the x, y are in same group
		return self.find(x) == self.find(y)
	
	def members(self, x):
		# return members of group
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]
	
	def roots(self):
		# return all roots
		return [i for i, x in enumerate(self.parents) if x < 0]
	
	def group_count(self):
		# return how many groups
		return len(self.roots())
	
	def all_group_members(self):
		# return all members of all groups
		return {r: self.members(r) for r in self.roots()}

n, m = map(int,input().split())
p = list(map(int,input().split()))
union = UnionFind(n)
ans = 0

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

for cnt, j in enumerate(p):
	if union.same(cnt, j-1):
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
 
N, M, *I = map(int, open(0).read().split())
P, XY = I[:N], I[N:]
 
uf = UnionFind(N + 1)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)
 
ans = 0
for i, p in enumerate(P, 1):
    if uf.same(i, p):
        ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def count(self, x):
        return -self.table[self._root(x)]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

N, M = map(int, input().split())
p = [int(i) for i in input().split()]
d = dict()
ins = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    ins.union(x, y)

ans = 0
for i, x in enumerate(p):
    if ins.find(i, x-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    #要素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]

    #xのグループとyのグループを併合
    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

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

uf = UnionFind(N)

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

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

Submission status: Accepted

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

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

lst = []
visited = [0]*N
for i in range(N):
    if visited[i] == 1:continue
    temp = [i]
    grp = [i]
    visited[i] = 1
    while temp:
        q = temp.pop()
        for gq in g[q]:
            if visited[gq] == 0:
                temp.append(gq)
                visited[gq] = 1
                grp.append(gq)
    lst.append(grp)

ans = 0
for l in lst:
    temp = set([p[i]-1 for i in l])
    ans += len(temp & set(l))
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
par=[i for i in range(n)]
 
def find(x):
  if par[x]==x:
    return par[x]
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy
 
f=lambda x:int(x)-1
for mm in range(m):
  x,y=map(f,input().split())
  union(x,y)
 
ans=0
for i in range(n):
  if find(p[i]-1)==find(i):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
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)
ans = 0
for i in range(n):
    if uf.find(i) == uf.find(p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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):
        ret = dict()
        for i in range(self.n):
            r = self.find(i)
            if r in ret:
                ret[r].append(i)
            else:
                ret[r] = [i]
        return ret

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


def main():
    N, M = in_nn()
    p = in_nl()

    uni = UnionFind(N)
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        uni.union(x, y)

    ans = 0
    for root, group in uni.all_group_members().items():
        s = set(group)
        for g in group:
            if p[g] - 1 in s:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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 = in_nn()
    p = in_nl()

    uni = UnionFind(N)
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        uni.union(x, y)

    edge = [[] for i in range(N)]
    for i in range(N):
        x = uni.find(i)
        edge[x].append(i)

    ans = 0
    for i in range(N):
        if edge[i]:
            s = set(edge[i])
            for e in edge[i]:
                if p[e] - 1 in s:
                    ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))

N, M, *I = map(int, open(0).read().split())
P, XY = I[:N], I[N:]

uf = UnionFind(N + 1)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

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

print(ans)

Submission status: Accepted

Solution code:
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()))
x = []
y = []
for i in range(M):
    in1, in2 = list(map(int,input().split()))
    x.append(in1)
    y.append(in2)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        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()))
    invP = [0] * N
    for i, x in enumerate(P): invP[x - 1] = i
    tree = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        tree.union(x-1, y-1)

    """
    i番の数字とi番の場所がpath-connectedだったらP[i]=iは実現可能。
    これを全ての頂点に関して実現可能な気がする。
    """

    ans = 0
    for i in range(N):
        if tree.same(i, invP[i]): ans += 1
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


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

GRAPH = [[] for _ in range(n)]
for _ in range(m):
    x, y = [int(xy) - 1 for xy in input().split()]
    GRAPH[x].append(y); GRAPH[y].append(x)

def dfs(now):
    searched[now] = True
    p = P[now]
    A[now] = B[p] = color
    for next in GRAPH[now]:
        if searched[next]:
            continue
        dfs(next)

A = [0] * n; B = [0] * n
searched = [False] * n
color = 1
for i in range(n):
    if searched[i]:
        continue
    dfs(i)
    color += 1

ans = sum(A[i] == B[i] for i in range(n))

print(ans)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
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=MI()
lis=LI()
u=UnionFind(n)
for i in range(m):
    x,y=MI()
    x-=1
    y-=1
    u.union(x,y)
count=0
for i in range(n):
    if u.find(lis[i]-1)!=u.find(i):
        count+=1
print(n-count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
N = N+1
L = [0] + IL()

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())
      
U = UnionFind(N)
for _ in range(M):
  u,v = IL()
  U.union(u,v)


DICMEM = DD(list)
DICNUM = DD(list)
for i in range(U.n):
  DICMEM[U.find(i)].append(i)
  DICNUM[U.find(i)].append(L[i])
count = 0
for r in U.roots():
  DICMEM[r].sort()
  DICNUM[r].sort()
  while DICMEM[r] and DICNUM[r]:
    if DICMEM[r][-1] == DICNUM[r][-1]:
      count += 1
      DICMEM[r].pop()
      DICNUM[r].pop()
    elif DICMEM[r][-1]>DICNUM[r][-1]:
      DICMEM[r].pop()
    else:
      DICNUM[r].pop()
print(count-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
xy=[list(map(int,input().split())) for _ in range(m)]
g=[[]for _ in range(n)]
for x,y in xy:
  g[x-1].append(y-1)
  g[y-1].append(x-1)
# 連結成分を探索
renktsu=[]
seen=[-1]*n
todo={i for i in range(n)}
while todo:
  t0=todo.pop()
  todo1=[t0]
  while todo1:
    t=todo1.pop()
    seen[t]=t0
    todo.discard(t)
    l=g[t]
    for li in l:
      if seen[li]==-1:
        todo1.append(li)
ans=0
for i in range(n):
  if seen[i]==seen[p[i]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
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()))
q = UnionFind(N)

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, 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

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

i2p = {}
p2i = {}

for i, pi in enumerate(p):
    i2p[i] = pi
    p2i[pi] = i

xy = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

uf = UnionFind(n)

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

ans = 0
for pi in p:
    if uf.find(pi) == uf.find(i2p[pi]):
        ans += 1

print(ans)

Submission status: Accepted

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