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

class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x):
        #要素xの根の番号を返す
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく(付け替える)
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
    def size(self, x):
        #要素xの所属するグループの頂点数を調べる
        #根のparentにサイズが格納されている
        return -self.parent[self.root(x)]
    def merge(self, x, y):
        #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        #大きい方(x)に小さい方(y)をくっつけたい
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))
    def all_family(self): # 根集合P, 子集合の集合C(C[P[i]]にはiを根とする子集合が入る)
        P = {} # 根のindexの集合はP.keys()で取得できる．これは根iが何番目の根かを返すdict
        now = 0
        for i in range(self.n):
            if self.parent[i] < 0:
                P[i] = now
                now += 1
        C = [[] for _ in range(len(P))] # P[i]
        for i in range(self.n):
            C[P[self.root(i)]].append(i)
        return P,C


p = list(map(int,input().split()))
UF = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    UF.merge(x-1,y-1)

ans = 0
_,C = UF.all_family()
for i in range(len(C)):
    S = C[i]
    T = [p[i]-1 for i in S]
    ans += len(set(S).intersection(set(T)))

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

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

# 木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

p = [0] + list(map(int,input().split()))

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect
N, M = map(int, input().split())
P = list(map(int, input().split()))
V = [[] for _ in range(N)]

for _ in range(M):
	x, y = map(int, input().split())
	V[x - 1].append(y - 1)
	V[y - 1].append(x - 1)
	
#labelはり
label = [-1] * N
label_num = 0

for i in range(N):
	if label[i] != -1: continue
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = label_num
		for adj in V[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	label_num += 1
	
# labelの番号(i)->labelの番号がiの頂点の集合
label_set = [[] for _ in range(label_num)]
for i in range(N):
	label_set[label[i]].append(i)
	
# 2分探索
def binary_search(val, lst):
	insert_place = bisect.bisect_left(lst, val)
	if len(lst) == insert_place: return False 
	return lst[insert_place] == val
	
ans = 0
for i in range(N):
	# 同じlabelを振ってある集合にP[i] - 1があるかを高速判定
	# print(P[i] - 1, label_set[label[i]])
	# print(binary_search(P[i] - 1, label_set[label[i]]))
	if binary_search(P[i] - 1, label_set[label[i]]):
		ans += 1
		
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
Pn = [int(i) for i in input().split()]
XYm = [[int(i) for i in input().split()] for _ in range(M)]

class UnionFind:
  def __init__(self, N, arr=None):
    if arr is None:
      self.roots = [-1 for i in range(N)]
      self.ranks = [0 for i in range(N)]
    else:
      self.roots = arr[:]
      self.ranks = [0 for i in range(N)]
            
  def root(self, i):
    root = self.roots[i]
    if root < 0:
      return i
    else:
      return self.root(root)
      
  def union(self, i, j):
    x = self.root(i)
    y = self.root(j)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.roots[x] = y
    else:
      self.roots[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1
  
  def same(self, i, j):
    return self.root(i) == self.root(j)
  
  def get_rank(self, i):
    root = self.root(i)
    return self.ranks[root]
  
uf = UnionFind(N)
for xy in XYm:
  x, y = xy
  uf.union(x-1, y-1)
  
count = 0
for i in range(N):
  count += 1 if uf.same(i, Pn[i]-1) else 0
print(count)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
P = LIST()
L = [LIST() for i in range(M)]

dic = defaultdict(list)
tree = UnionFind(N+1)
for a, b in L:
    tree.union(a, b)

# a = tree.all_group_members()

ans = 0
for i in range(1, N+1):
    if tree.find(i) == tree.find(P[i-1]):
        ans += 1
print(ans)
# print(a)
# for key, l in a.items():
#     for y in l:
#         dic[key].append(P[y-1])

# print(a)
# youso_set = set()
# graph_set = set()
# ans = 0
# for key, l in a.items():
#     if key == 0:
#         continue
#     youso_set = set(dic[key])
#     graph_set = set(l)
#     intersec = len(youso_set & graph_set)
#     ans += intersec
# print(ans)

Submission status: Accepted

Solution code:
# さっきWAして答えみて再度アタック
# （ちなみに問題自体憶えてないけど昔やったことあってそんときゃACしてたので退化してるね 向いてないね やめたほうがいいね）
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
par = [i for i in range(n)]


def root(x):
    # while x != par[x]:
    #     par[x] = root(par[x])
    # return par[x]
    # なぜか上記の書き方が駄目だった
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(a, b):
    if a > b:
        a, b = b, a
    ra, rb = root(a), root(b)
    if ra != rb:
        par[ra] = rb


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

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

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
ans = sum(u.same(p,i+1) for i,p in enumerate(p))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
ans = sum(1 if u.same(p,i+1) else 0 for i,p in enumerate(p))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
inf = [0]*(N+1)
for i in range(N):
  inf[p[i]] = i
ans = sum(1 if u.same(i,inf[i]+1) else 0 for i in range(1,N+1))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M, *L = map(int, open(0).read().split())
p = L[:N]
ls = L[N:]
u = UnionFind(N+1)
for x,y in zip(*[iter(ls)]*2):
  u.unit(x,y)
inf = {p[i]:i for i in range(N)}
ans = sum(1 if u.same(i,inf[i]+1) else 0 for i in range(1,N+1))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self,x,y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot

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.unite(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:
N,M=map(int,input().split())
p = list(map(int,input().split()))
for i in range(N): p[i] -= 1

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

def uf_root(a):
  if par[a] == a: return a
  par[a] = uf_root( par[a] )
  return par[a]

def uf_same(a,b):
  if (uf_root(a) ==uf_root(b)): return True
  return False

def uf_union(a,b):
  if (uf_same(a,b)): return
  a = uf_root(a)
  b = uf_root(b)
  par[a] = b
  return

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

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

Submission status: Accepted

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

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

def uf_root(a):
  if par[a] == a: return a
  par[a] = uf_root( par[a] )
  return par[a]

def uf_same(a,b):
  if (uf_root(a) ==uf_root(b)): return True

def uf_union(a,b):
  if (uf_same(a,b)): return
  a = uf_root(a)
  b = uf_root(b)
  par[a] = b
  return

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

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,M=map(int,input().split())
p=tuple(map(lambda x: int(x)-1,input().split()))
l=[[] for i in range(N)]
for i in range(M):
    x,y=map(lambda x: int(x)-1,input().split())
    l[x].append(y)
    l[y].append(x)
g=[None]*N
c=0
def hu(n,c):
    for i in l[n]:
        if g[i]==None:
            g[i]=c
            hu(i,c)
for i in range(N):
    if g[i]==None:
        g[i]=c
        hu(i,c)
        c+=1
a=0
for i in range(N):
    if g[i]==g[p[i]]:
        a+=1
print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

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

for i in range(N):
    p[i] -= 1

data = [[] for i in range(N)]

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

group = [0] * N
count = 1
for i in range(N):
    if group[i] != 0:
        continue
    group[i] = count
    stack = deque([[i,i]])
    while stack:
        x = stack.pop()
        for y in data[x[1]]:
            if y == x[0] or group[y] != 0:
                continue
            stack.append([x[1],y])
            group[y] = count
    count += 1

#print(group)

p_inv = [0] * N

for i in range(N):
    p_inv[p[i]] = i

ans = 0

for i in range(N):
    if group[i] == group[p_inv[i]]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


def main():
    N, M = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    u = UnionFind(N)
    for _ in range(M):
        x, y = [int(x) for x in input().split()]
        u.union(x - 1, y - 1)

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

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for _ in range(m)]
l=[i for i in range(n)]
def root(x):
  if x==l[x]:
    return x
  l[x]=root(l[x])
  return l[x]
for x,y in xy:
  a=root(x-1)
  b=root(y-1)
  if a!=b:
    l[b]=a
cnt=0
for i in range(n):
  if root(p[i]-1)==root(i):
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

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


N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
uf = UnionFind(N+1)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(p[x], p[y])
ans = 0
for i in range(1, N+1):
    if uf.same(i, 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 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())
uf = UnionFind(n+1)
P = list(map(int, input().split()))
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)

pos = dict()  # 整数pのインデックス
for i, p in enumerate(P):
    pos[p] = i+1
    
ans = 0
for i, p in enumerate(P):  
    if p == i + 1:  # 整数pとインデックスが一致している
        ans += 1
    else:  # 一致していないとき、入れ替え可能か
        index = pos[i+1]
        if uf.same(i+1, index):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
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 range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


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


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


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


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

count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i) else 0
print(count)

Submission status: Accepted

Solution code:
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 range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


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


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


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


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

count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i) else 0
print(count)

Submission status: Accepted

Solution code:
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 range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


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


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


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


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

count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i) else 0
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

par = [i for i in range(n)]
rank = [0 for _ in range(n)]


def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])  # 経路圧縮
    return par[x]


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


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


for x, y in xy:
    unite(x - 1, y - 1)


count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i - 1) else 0
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

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


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


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


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


for x, y in xy:
    unite(x - 1, y - 1)


count = 0
for i, p_i in enumerate(p):
    count += 1 if is_same(i, p_i - 1) else 0
print(count)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M = map(int, input().split())
    p = list(map(lambda a: int(a) - 1, input().split()))
    uf_tree = UnionFind(N)
    for _ in range(M):
        x, y = map(lambda a: int(a) - 1, input().split())
        uf_tree.union(x, y)
    
    ans = 0
    for pi in p:
        if uf_tree.same(pi, p[pi]):
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

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

N, M = map(int, input().split())
uf = UnionFind(N)
plist = list(map(int, input().split()))
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, plist[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


class UnionFind(object):

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



N, M = map(int, readline().split())
P = list(map(int, readline().split()))

uf = UnionFind(N)

for _ in range(M):
    x, y = map(int, readline().split())
    x -= 1
    y -= 1
    if uf.find(x) != uf.find(y):
        uf.unite(x, y)

cnt = 0

for i in range(N):
    if uf.find(i) == uf.find(P[i]-1):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

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 = MI()
	pp = LI1()
	uf = UnionFind(N)
	for _ in range(M):
		x,y = MI()
		x-=1
		y-=1
		uf.union(x,y)

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




if __name__ == '__main__':
	main()