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:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    p = [int(x) - 1 for x in input().split()]

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        x, y = (int(x) - 1 for x in input().split())
        g[x].add(y)
        g[y].add(x)

    roots = [-1] * N
    for r in range(N):
        if ~roots[r]: continue
        dq = deque()
        dq.append(r)
        roots[r] = r
        while dq:
            v = dq.popleft()
            for u in g[v]:
                if ~roots[u]: continue
                roots[u] = r
                dq.append(u)

    cnt = sum(1 for i, pi in enumerate(p) if roots[i] == roots[pi])
    print(cnt)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  #xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def union(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,M = map(int,input().split())
P = [0] + [int(i) for i in input().split()]
data = [list(map(int,input().split())) for i in range(M)]

A = UnionFind(N)

for i in range(M):
    A.union(data[i][0],data[i][1])
ans = 0
for i in range(1,N+1):
    if A.same_check(i,P[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

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

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

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

    if x == y:
      return

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

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

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

n,m=nii()
p=list(nii())

uf=UnionFind(n)

for i in range(m):
  x,y=nii()
  x-=1
  y-=1
  uf.union(x,y)

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

print(n-cnt)

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):  # 要素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が属するグループとを併合する
        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が属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        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():
    """
    <考察>
    (x, y)の組が与えられるが，親が一緒のところには自由に移動できる．
    UnionFind木で管理する．
    """
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = []
    for i in range(n):
        g.append((p[i] - 1, i))
    g.sort()  # p[i]でsort

    uf = UnionFind(n)
    for i in range(m):
        x, y = [int(i) - 1 for i in input().split()]
        uf.union(x, y)

    ans = 0
    for i in range(n):
        if uf.same(i, g[i][1]):
            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()))


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


G = unionFind(N)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        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] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/arc097/tasks/arc097_b

# 重要な性質
# swapできるidxは必ず任意に並び替えられる
# swapできるidxのグループがわかれば、そのなかでなるべく合うように並び替えられる
# union findか
# グループに分けてからidxの集合と、idxが指す要素の集合の積のサイズの合計が答え


N, M = read_ints()
P = read_ints()
uf = UnionFind(N)
for _ in range(M):
    x, y = read_ints()
    uf.unite(x - 1, y - 1)

group = defaultdict(lambda: set())
for i in range(N):
    group[uf.root(i)].add(i)

ans = 0
for g in group.values():
    tmp = set()
    for idx in g:
        tmp.add(P[idx] - 1)
    ans += len(tmp & g)
    # print(tmp, g)
print(ans)

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)]
li = [[] for _ in range(n+1)]
for x,y in xy:
    li[x].append(y)
    li[y].append(x)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uni = UnionFind(n+1)
for i in range(n+1):
    for j in li[i]:
        uni.union(i,j)

point = 0

for i in range(n):
    if uni.same(i+1,p[i]):
        point += 1

print(point)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
p = [int(i) for i in input().split()]
par = [-1]*n
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def same(x,y):
    return find(x) == find(y)
  
for i in range(m):
  x,y = [int(i) for i in input().split()]
  unite(x-1,y-1)
  
ans = 0
for i,pi in enumerate(p):
  if pi == i+1:
    ans += 1
  else:
    if same(pi-1,i):
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
P=list(map(int, input().split()))
class UnionFind():
  # 作りたい要素数nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1)
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
  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):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合
    if (x == y):
      return 
      # 違う木に属していた場合rnkを見てくっつける方を決める
      #rnkが大きい方に結合
    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
      # rnkが同じ（深さに差がない場合）は1増やす
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uni=UnionFind(N)
for i in range(M):
  x,y=map(int, input().split())
  uni.Unite(x,y)
  
ans=0 
for i, p in enumerate(P):
  if uni.isSameGroup(p,i+1):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
seen = [False]*(n+1)
ans = 0
for i in range(1, n+1):
    if seen[i] or len(graph[i])==0:
        continue
    queue = deque([i])
    seen[i] = True
    inds = {i}
    ps = {p[i-1]}
    while len(queue)>0:
        node = queue.popleft()
        for c_node in graph[node]:
            if seen[c_node]:
                continue
            seen[c_node] = True
            inds.add(c_node)
            ps.add(p[c_node-1])
            queue.append(c_node)
    ans += len(inds&ps)
for ind, i in enumerate(p):
    if seen[ind+1]:
        continue
    if ind+1==i:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n+1)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x,y)
ans=0
for i in range(n):
  if uf.same(p[i],i+1):
    ans+=1
print(ans)

Submission status: Accepted

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

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    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] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-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
            

uni = UnionFind(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    uni.connect(x, y)

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

print (ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    P = [int(i)-1 for i in input().split()]

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

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

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

    def size(x):
        return rank[find_root(x)]

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

    ans = 0
    for i, p in enumerate(P):
        if is_same_group(i, p):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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())

idx = [0] * N
for i, p in enumerate(map(int,input().split())):
    idx[p - 1] = i

UF = UnionFind(N)

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

ans = 0
for n in range(N):
    if UF.same(n, idx[n]):
        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(10 ** 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 = map(int, readline().split())
p = list(map(int, readline().split()))
xy = [list(map(int, readline().split())) for _ in range(m)]
uf = UnionFind(n + 1)
cnt = 0
for x, y in xy:
    uf.union(x, y)
for i, check in enumerate(p):
    if uf.same(i + 1, check):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
pi = [int(i) for i in input().split()]

xy = [[] for j in range(n+1)]

for i in range(m):
    x,y = map(int,input().split())
    xy[x].append(y)
    xy[y].append(x)
    
path = [[] for i in range(n+1)]
#check = [0] * (n+1)

check = [-1]*(n+1)

def dfs(x,check):
    #if check[x] != -1:
    #    return
    for i in range(len(xy[x])):
        cho = xy[x][i]
        #print(cho,x)
        if check[cho] != -1:
            continue
        check[cho] = num
        dfs(cho,check)
    
    return

num = 0
for i in range(1,n+1):
    #print(i,check[i])
    if check[i] != -1:
        continue
    if len(xy[i]) == 0:
        continue
    dfs(i,check)
    num += 1
#print(check)
ans = 0

for i in range(1,n+1):
    if pi[i-1] == i:
        ans += 1
    elif check[pi[i-1]] == -1:
        continue
    elif check[i] == check[pi[i-1]]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf={i:i for i in range(1,n+1)}
def get_p(i):
    lst=[]
    while uf[i]!=i:
        lst.append(i)
        i=uf[i]
    for l in lst[:-1]:
        uf[l]=i 
    return i 

def unite(i,j):
    uf[get_p(i)]=get_p(j)
def same(i,j):
    return get_p(i)==get_p(j)

def main():
    for i in range(m):
        x,y=map(int,input().split())
        unite(x,y)
    cnt=0
    for i in range(1,n+1):
        cnt+=same(p[i-1],uf[i])
    print(cnt)    
if __name__=='__main__':
    main()

Submission status: Accepted

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

P=list(map(int,input().split()))
P=list(map(lambda x:x-1,P))

# Pもx,yも0-indexに変更
# UnionFindで、(x,y)で同組になるインデックスの集合を求める。
# 同じインデックスの集合に存在するPの値の集合で、インデックスの集合にも存在するものの数が答え

# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
UF=UnionFind(N)
for i in range(M):
  x,y = map(int,input().split())
  UF.unite(x-1,y-1)
  
from collections import defaultdict
dic = defaultdict(list)
for i in range(N):
  r = UF.root(i)
  dic[r].append(i)
  
ans = 0
for inds in dic.values():
  vals = set()
  for i in inds:
    vals.add(P[i])
  ans += len(vals & set(inds))
  
print(ans)

Submission status: Accepted

Solution code:
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)
        
n,m = map(int,input().split())
L = list(map(int,input().split()))

UFind = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    UFind.union(a-1,b-1) 
cnt = 0   

for i in range(n):
    if UFind.same_check(i,L[i]-1):
        cnt +=1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

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


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf = UnionFind(n)

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

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  # 作りたい要素数nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n+1)
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
  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):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合
    if (x == y):
      return 
      # 違う木に属していた場合rnkを見てくっつける方を決める
      #rnkが大きい方に結合
    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
      # rnkが同じ（深さに差がない場合）は1増やす
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  # ノードxが属する木のサイズを返す
  def Count(self, x):
    return -self.root[self.Find_Root(x)]


N,M=map(int, input().split())
P=list(map(int, input().split()))
uni=UnionFind(N)
for i in range(M):
  x,y=map(int, input().split())
  uni.Unite(x-1,y-1)
  
ans=0
for i,p in enumerate(P):
  if uni.isSameGroup(i,p-1):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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())
pos = [0] * N
for idx, p in enumerate(map(int,input().split())):
    pos[p - 1] = idx

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

ans = 0
for n in range(N):
    if UF.same(pos[n], n):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_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.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  # print 表示用
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())


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

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

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.is_same(i, p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *P,=map(int, input().split())
    P=[-1]+P
    uf=UnionFindTree(N+1)
    for _ in range(M):
        x,y=map(int, input().split())
        uf.union(P[x],P[y])
    ans=0
    for i in range(1,N+1):
        if uf.same(P[i], i): ans+=1
    print(ans)

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()