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:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 6)


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

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

result = 0
for i in range(N):
    if find(parent, i) == find(parent, p[i] - 1):
        result += 1
print(result)

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
P = list(int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(m)]

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個の要素を0 ~ n - 1の番号で管理する。以下の属性およびメソッドを持つ。

    parents
    各要素の親要素の番号を格納するリスト
    要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    find(x)
    要素xが属するグループの根を返す

    union(x, y)
    要素xが属するグループと要素yが属するグループとを併合する

    size(x)
    要素xが属するグループのサイズ（要素数）を返す

    same(x, y)
    要素x, yが同じグループに属するかどうかを返す

    members(x)
    要素xが属するグループに属する要素をリストで返す

    roots()
    すべての根の要素をリストで返す

    group_count()
    グループの数を返す

    all_group_members
    {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す

    __str__()
    print()での表示用
    ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """

uf = UnionFind(n+1)
for x, y in XY:
    uf.union(x, y)

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

Submission status: Accepted

Solution code:
# 下記ページを参考に実装してる
# https://qiita.com/ofutonfuton/items/550c984f08e39a189ca6#d%E5%95%8F%E9%A1%8C
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()))

tree = UnionFind(n)

for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  tree.union(x, y)
#print(tree)
ans = 0
for i in range(n):
  if tree.same(i, p[i]-1):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
N,M = I()
p = l()
ans = 0
u = UnionFind(N)
for i in range(M):
    a,b = I()
    u.unite(a-1,b-1)
for i in range(N):
    if p[i] == i+1:
        ans += 1
    elif u.find_root(i) == u.find_root(p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

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

    # 要素xの根の値を取得
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    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 resolve():
    N, M = list(map(int, input().split()))
    P = list(map(int, input().split()))
    XY = [list(map(int, input().split())) for _ in range(M)]
    uf = UnionFind(N)
    for xy in XY:
        uf.union(xy[0]-1, xy[1]-1)
    cnt = 0
    for i in range(N):
        if uf.same(i, P[i]-1):
            cnt += 1

    print(cnt)
    
    
if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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 = map(int, readline().split())
    p = list(map(int, readline().split()))
    uf = UnionFind(n + 1)

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

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

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

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

        if x == y:
            return

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

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

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

N, M = getNM()
# 1 ~ 5の並び替え
# これを1, 2, 3, 4, 5にしたい
P = getList()
# Pのうちのペア
query = []
for i in range(M):
    a, b = getNM()
    query.append([a, b])

U = UnionFind(N)
for i in range(M):
    a, b = query[i]
    U.union(a - 1, b - 1)

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

print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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)

        # 連結成分の大きさを返す
        def size(self, x):
            return -self.parents[self.find(x)]

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

    idx = [0] * n
    for i in range(n):
        idx[P[i] - 1] = i

    res = 0
    for j in range(n):
        if j + 1 != P[j]:
            if uf.same(j, idx[j]):
                res += 1
        else:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

    def print(self):
        print(self.p)
        
def readinput():
    n,m=list(map(int,input().split()))
    p=list(map(int,input().split()))
    p.insert(0,0)
    pairs=[]
    for _ in range(m):
        pair=list(map(int,input().split()))
        pairs.append(pair)
    return n,m,p,pairs

def main(n,m,p,pairs):
    uft=DisjointSet(n+1)
    for x,y in pairs:
        if uft.same(x, y):
            pass
        else:
            uft.unite(x, y)

    #uft.print()

    #print(p)
    count=0
    for i in range(1,n+1):
        if uft.same(i,p[i]):
            #p[i],p[j] = p[j], p[i]
            count+=1
    
    return count

if __name__=='__main__':
    n,m,p,pairs=readinput()
    ans=main(n,m,p,pairs)
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


def main():
    def find(x):
        parent = data[x]
        if parent < 0: return x
        root = find(parent)
        data[x] = root
        return root

    def union(x, y):
        root, second = find(x), find(y)
        if root == second: return False
        if data[root] > data[second]:
            second, root = root, second
        data[root] += data[second]
        height[root] = max(height[root], height[second]+1)
        data[second] = root
        return True

    def size(x):
        return -data[find(x)]

    N, M = lr()
    P = lr()
    data = [-1] * (N+1)  # 1-indexed rootには-sizeが入る
    height = [0] * (N+1)

    for _ in range(M):
        x, y = lr()
        union(x, y)
    
    answer = 0
    for i in range(N):
        if find(i+1) == find(P[i]):
            answer += 1
    
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(a,b):
  ra=find(a)
  rb=find(b)
  if ra!=rb:
    par[ra]=par[rb]
 
for i in range(m):
  v,w=map(f,input().split())
  union(v,w)
 
ans=0
for j in range(n):
  if find(j)==find(p[j]):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
p=list(map(f,input().split()))
par=[j for j in range(n)]
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(a,b):
  ra=find(a)
  rb=find(b)
  if ra!=rb:
    par[ra]=rb
 
for i in range(m):
  v,w=map(f,input().split())
  union(v,w)
 
ans=0
for j in range(n):
  if find(j)==find(p[j]):
    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.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x): # xが属するグループのサイズを返す
        return -self.root[self.Find_Root(x)]
    def Members(self, x): # xが属するグループに属する要素をリストで返す
        return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
    def Roots(self): # 全ての根の要素をリストで返す
        return [i for i, x in enumerate(self.root) if x < 0]
    def Group_Count(self): # グループの数を返す
        return len(self.Roots())
    
N, M = map(int, input().split())
uf = UnionFind(N+1)
p = list(map(int, input().split()))
roots = {i:i for i in range(N)}
proots = {i:i for i in range(N)}
for _ in range(M):
    x, y = map(lambda x:int(x)-1, input().split())
    uf.Unite(x, y)

for i in range(N):
    r = uf.Find_Root(i)
    roots[i] = r
    proots[p[i]-1] = r 

ans = 0
for i in range(N):
    if roots[i] == proots[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
XY = list(list(map(lambda x: int(x)-1, input().split())) for _ in range(m))
G = [[] for _ in range(n)]
for x, y in XY:
    G[x].append(y)
    G[y].append(x)

q = deque()
vis = [False]*(n)
ans = 0
for i in range(n):
    set_x, set_px = set(), set()
    q.append(i)
    while q:
        x = q.popleft()
        if vis[x]: continue
        vis[x] = True
        set_x.add(x)
        set_px.add(P[x])
        for y in G[x]:
            if vis[y]: continue
            q.append(y)
    ans += len(set_x & set_px)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int, input().split())
P = [0]+list(map(int, input().split()))
XY = list(list(map(int, input().split())) for _ in range(m))
G = [[] for _ in range(n+1)]
for x, y in XY:
    G[x].append(y)
    G[y].append(x)

q = deque()
vis = [False]*(n+1)
ans = 0
for i in range(1,len(G)):
    set_x, set_px = set(), set()
    q.append(i)
    while q:
        x = q.popleft()
        if vis[x]: continue
        vis[x] = True
        set_x.add(x)
        set_px.add(P[x])
        for y in G[x]:
            if vis[y]: continue
            q.append(y)
    ans += len(set_x & set_px)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
P = [0]+list(map(int, input().split()))
XY = list(list(map(int, input().split())) for _ in range(m))
G = [[] for _ in range(n+1)]
for x, y in XY:
    G[x].append(y)
    G[y].append(x)

# print(n,m)
# print(P)
# print(XY)
# print(G)
# for i in range(len(G)):#########
#     print(i, G[i])###############

from collections import deque
q = deque()
vis = [False]*(n+1)
ans = 0
for i in range(1,len(G)):
    # print('i',i, 'G[i]',G[i])
    inc_x = set()
    inc_px = set()
    q.append(i)
    while q:
        # print(q)
        x = q.popleft()
        if vis[x]: continue
        vis[x] = True
        inc_x.add(x)
        inc_px.add(P[x])
        # print('x',x,'P[x]',P[x],'G[x]',G[x])
        for y in G[x]:
            # print('y',y)
            if vis[y]: continue
            q.append(y)
    # print('inc_x',inc_x)
    # print('inc_px',inc_px)
    # print('inc_x&inc_px',inc_x&inc_px)
    # print('len(inc_x&inc_px)',len(inc_x&inc_px))
    ans += len(inc_x & inc_px)

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 root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

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

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

def main():
    N, M, *PXY = map(int, open(0).read().split())
    P = PXY[:N]
    # print(N, M, PXY)
    uf = UnionFind(N + 1)
    for i in range(M):
        x, y = PXY[N + 2*i + 0], PXY[N + 2*i + 1]
        uf.unite(x, y)
    ans = 0
    for i in range(N):
        is_same = uf.same(i + 1, P[i])
        if is_same:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n
        self._rank = [0]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        elif self._rank[x] > self._rank[y]:
            self._table[x] += self._table[y]
            self._table[y] = x
        else:
            self._table[y] += self._table[x]
            self._table[x] = y
            if self._rank[x] == self._rank[y]:
                self._rank[y] += 1
    
    def find(self, x, y):
        return self._root(x) == self._root(y)

    def count(self, x):
        return -self._table[self._root(x)]
    
    def __str__(self):
        return str(list(self))
    def __repr__(self):           
        return repr(list(self))
    def __iter__(self):
        return (self._root(i) for i in range(n))
    def __list__(self):
        return list(iter(self))

from collections import defaultdict
n, m, *X = map(int, open(0).read().split())
P, XY = X[:n], X[n:]

uf = UnionFind(n)
for x, y in zip(XY[::2], XY[1::2]):
    uf.unite(x-1, y-1)
group = list(uf)

d1 = defaultdict(set)
d2 = defaultdict(set)
for i, n in enumerate(group, 1):
    d1[n].add(i)
    d2[n].add(P[i-1])

ans = 0
for i in set(group):
    ans += len(d1[i] & d2[i])
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

from collections import defaultdict
g = defaultdict(list)
for x, y in xy:
    x, y = x - 1, y - 1
    g[x].append(y)
    g[y].append(x)

visited = [0] * n
ans = 0

for i in range(n):
    if visited[i] == 0:
        q = [i]
        visited[i] = 1
        s = set([i])
        while q:
            cur = q.pop()
            for target in g[cur]:
                if visited[target] == 0:
                    visited[target] = 1
                    q.append(target)
                    s.add(target)

        ps = set()
        for j in s:
            ps.add(p[j] - 1)

        intersect = s & ps
        ans += len(list(intersect))
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 = map(int, input().split())
s = 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.unit(a, b)

ans = 0
for i, p in enumerate(s):
    if u.same(i, p - 1):
        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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

N,M,*f = map(int, open(0).read().split())
p = f[:N]
xy = [f[N+2*i:N+2*i+2] for i in range(M)]
uf = UnionFind(N+1)
for x, y in xy:
    uf.union(x,y)
ans = 0
for i in range(1,N+1):
    if p[i-1] == i:
        ans += 1
    else:
        if uf.find(p[i-1]) == uf.find(i):
            ans += 1
        elif uf.find(i) < 0:
            if uf.find(p[i-1]) == i:
                ans += 1
        elif uf.find(p[i-1]) < 0:
            if uf.find(i) == p(i-1):
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

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

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

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

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count


from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    a=list(map(int,readline().split()))
    uf=UnionFind(n+1)
    for i in range(m):
        x,y=map(int,readline().split())
        uf.union(x,y)

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

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

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

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

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count


from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    a=list(map(int,readline().split()))
    uf=UnionFind(n+1)
    for i in range(m):
        x,y=map(int,readline().split())
        uf.union(x,y)

    i=1
    while i<n+1:
        x=a[i-1]
        if x==i:
            i+=1
        elif uf.are_same(i,x):
            a[i-1],a[x-1]=a[x-1],a[i-1]
        else:
            i+=1

    print(len([a[i] for i in range(n) if a[i]-1==i]))

if __name__=="__main__":
    main()