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:
from sys import stdin
readline = stdin.buffer.readline
read = stdin.buffer.read
def i_input(): return int(input().rstrip())
def i_map(): return map(int, input().rstrip().split())
def i_list(): return list(i_map())

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

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

    def unite(self, x, y) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        return True

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

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

    def is_same(self, x, y) -> bool:
        return self.root(x) == self.root(y)

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

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

def main():
    N, M = i_map()
    u = UnionFind(N)
    P = i_list()
    for _ in range(M):
        x, y = i_map()
        u.unite(x, y)
    ans = 0
    for i, p in enumerate(P, 1):
        if u.is_same(i, p):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

xy = [[] for i in range(n)]
for i in range(m):
  x, y = map(int, input().split())
  x,y = x-1,y-1
  xy[x].append(y)
  xy[y].append(x)
visited = [0 for i in range(n)]

def dfs(s,cnt):
  visited[s] = cnt
  for i in xy[s]:
    if visited[i] == 0:
      dfs(i,cnt)

cnt = 0
for i in range(n):
  if visited[i]:
    continue
  cnt += 1
  dfs(i,cnt)
ans = 0
for i in range(n):
  if visited[p[i]] == visited[i]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - Equals
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return
# xとyが同じ集合に属するか
def same(x,y):
    return find(x) == find(y)
#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,M = map(int,readline().split())
P = list(map(int,readline().split()))
# 0-index
par = [-1]*(N+1)

for _ in range(M):
    x,y = map(int,readline().split())
    union(x,y)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

    def root(self, i):
        if self.parent[i] < 0:
            return i

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

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

    def size(self, i):
        return -self.parent[self.root(i)]

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

forest = UnionFind(N)

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

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

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()))
Network = UnionFind(N)

for i in range(M):
    X,Y = list(map(int,input().split()))
    Network.union(X-1, Y-1)

out=0
for i in range(N):
    if Network.find(i)==Network.find(P[i]-1):
        out+=1
print(out)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
        T_1 = list(set(OK + Enable))
        T_2 = list(set(OK + Origin))
        ans = max(ans, len(T_1) + len(T_2) - len(set(T_1 + T_2)))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n): # 初期化。1スタートで設計
        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)

    # 全ての親の検索（一括での経路圧縮）
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

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

uf = UnionFind(n)
for x,y in pab:
    uf.union(x,y)

uf.all_find()

cnt = 0
for i,k in enumerate(p):
    if k == i+1: # そもそもカウントできる場所にいる場合
        cnt += 1
    else:
        if uf.same_check(i+1,k):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n): # 初期化。1スタートで設計
        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())
p = list(map(int, input().split()))
pab = [list(map(int, input().split())) for i in range(m)]

uf = UnionFind(n)
for x,y in pab:
    uf.union(x,y)

cnt = 0
for i,k in enumerate(p):
    if k == i+1: # そもそもカウントできる場所にいる場合
        cnt += 1
    else:
        if uf.same_check(i+1,k):
            cnt += 1
print(cnt)

Submission status: Accepted

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

parent = [i + 1 for i in range(n)]
rank = [0 for i in range(n)]

def find(x):
    if parent[x - 1] == x:
        return x
    else:
        parent[x - 1] = find(parent[x - 1])
        return parent[x - 1]

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

for i in range(m):
    x, y = map(int, input().split())
    unite(x, y)
dic = {}
for i in range(n):
    dic.setdefault(find(i + 1), [set(), set()])
    dic[find(i + 1)][0].add(i + 1)
    dic[find(i + 1)][1].add(p[i])
ans = 0
for i in dic.values():
    ans += len(i[0] & i[1])
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数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):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



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.union(x,y)
ans = 0
for i in range(1, 1+N):
    if p[i]==i:
        ans += 1
    else:
        if uf.same(i, p[i]):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = tuple(map(int, input().split()))
A = []
for _ in range(M):
    i, k = map(int, input().split())
    A.append((i-1, k-1))
class Union():
    def __init__(self, n):
        self.para = [-1] * n
    
    def find(self, n):
        if self.para[n] < 0:
            return n
        
        else:
            self.para[n] = self.find(self.para[n])
            return self.para[n]
    
    def union(self, n, m):
        n = self.find(n)
        m = self.find(m)
        if n == m:
            return False
        else:
            if self.para[n] > self.para[m]:
                n, m = m, n
            
            self.para[n] += self.para[m]
            self.para[m] = n
    
    def same(self, n, m):
        return self.find(n) == self.find(m)
ut = Union(N)
for i,k in A:
    ut.union(i, k)
for i in range(N):
    ut.find(i)

cnt = 0
for i in range(N):
    if P[i] == i + 1:
        cnt += 1
    else:
        if ut.same(P[i]-1, i):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")


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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]
uni = UnionFind(N + 1)
for xyi in xy:
    x, y = xyi
    uni.union(x, y)
cnt = 0
for i, pi in enu(p):
    if uni.same_check(i + 1, pi):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
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])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする（出来るだけ浅い木にするため）
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

    def size(self, x):                                          # xの根のparent（= 要素数）を返す
        return -self.parents[self.find(x)]

    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):                                          # print(self) での返し方を定義
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

##############################################################################################################
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
P = list(map(int, input().split()))
U = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    U.union(a, b)
res = 0
for i, p in enumerate(P):
    if U.same(p-1,i):
        res += 1
print(res)

Submission status: Accepted

Solution code:
# UnionFind、0-index
#############################################################


class UnionFind:

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

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################
# (x,y)をuniteする
# i = 1,2,...,Nについて、
# iとp[i-1]が同じ連結成分に含まれるならば、p_i = iとすることができる

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

uf = UnionFind(N + 1)

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

Submission status: Accepted

Solution code:
n,n_pairs = map(int,input().split())
p_ls = 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):
        '''
        注意：0-idx
        '''
        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 i in range(n_pairs):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)

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

Submission status: Accepted

Solution code:
class uft():
    def __init__(self,n):
        self.p=[ -1 for i in range(n)]
        self.r=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
            
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
            
        if(x!=y):
            self.p[x]=y
        return
    
n,m=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
  p[i]-=1
uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
for i in range(n):
    if(uf.find(i)==uf.find(p[i])):
        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()))
q = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]

par = [x for x in range(n)]
rank = [0]*n

def find(x):
  if par[x] == x:
    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
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]: rank[x] += 1

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

for x, y in q:
  unite(x, y)
#print(par)
#print(rank)
ans = 0
for i in range(n):
  if same(p[i], i): ans += 1
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
    
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
  
ans=0
  
for i in range(n):
  if find(p[i]-1)==find(i):
    ans+=1
    

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
par=[i for i in range(N)]
size=[1 for i in range(N)]
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)
count=0
for i in range(N):
  if find(i)==find(P[i]):
    count+=1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


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

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

    roots = uf.roots()
    sets_dict = {}
    members_dict = {}
    for i in roots:
        sets_dict[i] = set([])
        members_dict[i] = set([])

    for i in range(n):
        root = uf.find(i)
        sets_dict[root].add(p[i])
        members_dict[root].add(i)
        # print(i, root)
    # print(sets_dict)
    # print(members_dict)
    ans = 0
    for i in roots:
        ans += len(sets_dict[i] & members_dict[i])
    print(ans)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
'''
N, M = mi()
P = li()
tmp = []


for i in range(M):
    x, y = mi()
    x, y = x-1, y-1
    if x > y:
        x, y = y, x
    tmp.append([x, y])

xy = []

sorted(tmp, key=lambda x : x[0])
print(tmp)
now = tmp[0][0]
flag = [0] * N
tmp2 = [now]
num = 1
flag[tmp[0][0]] = num
for x, y in tmp:
    if x != now:
        xy.append(tmp2)
        tmp2 = [x]
        now = x
        num += 1
        flag[x] = num
    tmp2.append(y)
    flag[y] = num

if tmp2:
    xy.append(tmp2)

print(flag)
print(xy)

for i in range(N):
'''
class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N, M = mi()
P = li()
G = UnionFind(N)
ans = 0

for i in range(M):
    x, y = mi()
    G.unite(x-1, y-1)
    
for i in range(N):
    if G.same(P[i]-1, i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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)


def main():
    N, M = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    XY = map(int, read().split())

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

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

    print(ans)
    return


if __name__ == '__main__':
    main()