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:
import sys
input = sys.stdin.readline

n, m = [ int(v) for v in input().split() ]
num = [ int(v)-1 for v in input().split() ]
parent_list = [ i for i in range(n) ]

def root(x):
    while parent_list[x] != x:
        parent_list[x] = parent_list[parent_list[x]]  
        x = parent_list[x]   
    return x

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    ra, rb = root(a), root(b)
    if ra != rb:
        parent_list[ra] = rb
        
ans_list = []
for i, v in enumerate(num):
    if root(i) == root(v):
        ans_list.append(True)
    else:
        ans_list.append(False)

print(ans_list.count(True))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
 
a=[int(i) for i in range(n)]

def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
p=list(int(i)-1 for i  in input().split())
pp=p
ans=0
#007映画　4/10
s=[list(int(i)-1 for i  in input().split()) for _ in range(m)]
for x, y in s:
    unite(a,x,y)
for i in range(n):
    if find(a,i)==find(a,pp[i]):
        ans+=1

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

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

cnt = 0
for i,j in enumerate(ps):
    if uf.same_check(i+1 , j):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

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

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

c=0
for i in range(N):
	if same(i,e[i]):
		c+=1

print(c)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, N):
    self.par = [i for i in range(N)]
 
  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    self.par[self.root(y)] = self.root(x)
    
  def same(self, x, y):
    return self.root(x) == self.root(y)

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

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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, N):
    self.par = [i for i in range(N)]
 
  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    self.par[self.root(y)] = self.root(x)
    
  def same(self, x, y):
    return self.root(x) == self.root(y)

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

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

Submission status: Accepted

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

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 solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(x[i]-1,y[i]-1)

    answer = 0

    for j in range(N):
        if uf.same(p[j]-1,j):
            answer +=1        
        
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    main()

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

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
# ノイローゼなりかけたので答え見た
# unionfind使うのはわかったけど与えられた配列とどうやって合わせて実装するかわからずさらにノイローゼに


n, m = map(int, input().split())

arr = list(map(lambda x: int(x) - 1, input().split()))
par = [i for i in range(n)]


def root(i):
    if i == par[i]:
        return i
    else:
        _i = root(par[i])
        par[i] = _i
        return _i


def union(x, y):
    x, y = root(x), root(y)
    if x != y:
        # yの親をxにする
        par[y] = x


def same(nx, ny):
    return root(nx) == root(ny)


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

ans = 0
for i in range(n):
    if same(i, arr[i]):
        ans += 1
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(' '))
P = [int(c) for c in input().split(' ')]

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

ans = 0
for i in range(N):
    if i+1 == P[i]:
        ans += 1
    else:
        if uft.find(i) == uft.find(P[i]-1):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]
par = [i for i in range(N+1)]
rank = [0] * (N+1)
 
def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]
 
def union(x,y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
 
def check_same(x,y):
    return find(x) == find(y)
 
for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    union(x,y)
ans = 0
for i in range(1,N+1):
    if find(i) == find(P[i-1]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]
par = [i for i in range(N+1)]
rank = [0] * (N+1)

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

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

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

for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    union(x,y)
ans = 0
for i in range(1,N+1):
    if find(i) == find(P[i-1]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(1000000)
d1=defaultdict(list)
d2=defaultdict(list)
n,m=map(int,input().split())
l=list(map(int,input().split()))
la=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  la[a].append(b)
  la[b].append(a)
lb=[0 for i in range(n+1)]
def dfs(x,y):
  if lb[x]!=0:
    return
  else:
    lb[x]=y
    s=la[x]
    if s==[]:
      pass
    else:
      for i in s:
        dfs(i,y)
c=1
for i in range(1,n+1):
  dfs(i,c)
  c+=1
lc=set(lb)
for i in range(1,n+1):
  d1[lb[i]]+=[i]
  d2[lb[i]]+=[l[i-1]]
ans=0
for i in d1:
  d11=d1[i]
  d12=d2[i]
  for j in d12:
    index=bisect.bisect_right(d11,j)
    if d11[index-1]==j:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = Uf(N+1)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)
    ans = 0
    for i, p in enumerate(P, 1):
        if uf.same(i, p):
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N, M = list(map(int, input().split()))
P = list(map(int, input().split()))
L = [None]*N
for l, p in enumerate(P):
    L[p-1] = l
uf = UF(N)
for _ in range(M):
    x, y = list(map(int, input().split()))
    uf.union(x-1, y-1)

ans = 0
for i in range(N):
    if uf.find(i)==uf.find(L[i]): ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    perm=list(map(lambda x:int(x)-1,input().split()))
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    # 連結成分ごとに分解する
    cnt=[0]
    comp=[-1]*n
    def dfs(v)->NoneType:
        if(comp[v]!=-1): return
        cnt[0]+=1
        comp[v]=cnt[0]
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(comp[nv]!=-1): continue
                comp[nv]=cnt[0]
                Q.append(nv)

    for v in range(n): dfs(v)
    print(sum(1 for v in range(n) if(comp[v]==comp[perm[v]])))
resolve()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
ps = ril()
ls = rils(m)

uf = UnionFind(n)
for a, b in ls:
    uf.merge(a - 1, b - 1)
res = 0
for i in range(n):
    p0 = uf.get_root(i)
    p1 = uf.get_root(ps[i] - 1)
    if p0 == p1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

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

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

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


n, m = LI()
P = LI()
uf = UnionFind(n)
for _ in range(m):
    x, y = LI()
    uf.union(x - 1, y - 1)



print(sum([bool(uf.is_same(P[i] - 1, i)) for i in range(n)]))

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+1)
for i in range(M):
    a, b = map(int,input().split())
    uf.union(a,b)
ans = 0
for i in range(1,N+1):
    if uf.same(i,P[i-1]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

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

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

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


def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        uf.union(x-1, y-1)
    ans = 0
    for i in range(N):
        if uf.same(P[i]-1, i):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

import random

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):       # 2つのデータxとyが同じ木に属するならtrue，そうでなければfalseを返す
        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_len_of_seq, m_num_of_pairs = map(int, input().split())
    union_find_forest = UnionFind(n_len_of_seq) # 数列の長さだけの木からなるunion_find森を作る
    p_seq  = list(map(int, input().split()))
    p_seq = [p_seq[i] - 1 for i in range(len(p_seq))]

    # eprint("union_find_forest")
    # eprint(union_find_forest)
    # eprint()

    for index in range(m_num_of_pairs): # loop for each element (pair) in pairs
        x_pair,y_pair = map(int, input().split())
        x_pair-=1
        y_pair-=1
        union_find_forest.union( x_pair , y_pair) # x_pair-1の木とy_pair-1の木を併合する
        # eprint(union_find_forest)
        # eprint()
        
    cnt=0
    for i in range(n_len_of_seq): # loop for p_seq (sequence of integeres)
        if union_find_forest.same(i, p_seq[i]): # 例えばp_seqのindex==3であるところ(p_seqの4番目)(値は4であって欲しい)について，うにふぁい森の中で4とp_seq[3](の値)が同じ木に属していれば，それらを交換できる(何回でもペア交換は適用できるからね)(連結成分のなかは自由自在に入れ替えられる)．
            # やっぱバグるので全部 0 based index に直しました
            cnt+=1
    
    print(cnt)
    # p_seq = list(map(int, input().split()))
    # pairs=[[0,0] for _ in range(m_num_of_pairs)]
    # # eprint(pairs)
    # for index_pairs in range(m_num_of_pairs):
    #     pairs[index_pairs][0] , pairs[index_pairs][1] = map(int, input().split())
    #     # eprint(index_pairs)
    #     # eprint(pairs[index_pairs])
    #     # eprint(pairs)
    # eprint(pairs)

    
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = 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 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
        else:
            self.PAR[y] = x
            if self.RANK[x] == self.RANK[y]:
                self.RANK[x] += 1

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

N,M = map(int,input().split())
Data = list(map(int,input().split()))
graph = UnionFind(N+1)
for _ in range(M):
    x1,y1 = map(int,input().split())
    graph.union(x1,y1)

ans = 0
for i in range(1,N+1):
    if graph.same(i,Data[i-1]):
        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()))


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

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


d = DisjointSet(N)
for i in range(M):
    xi, yi = map(int, input().split())
    d.unite(p[xi - 1], p[yi - 1])

ans = 0
for i in range(N):
    if d.find(p[i]) == d.find(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def par(a):
    if P[a] < 0: return a
    t = par(P[a])
    P[a] = t
    return t
def unite(a, b):
    if par(a) == par(b): return 0
    if P[par(b)] == P[par(a)]:
        P[par(b)] = par(a)
        P[par(a)] -= 1
    elif P[par(b)] > P[par(a)]:
        P[par(b)] = par(a)
    else:
        P[par(a)] = par(b)

N, M = map(int, input().split())
P = [-1 for i in range(N)]
A = [int(a)-1 for a in input().split()]
for _ in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)

X = [[] for _ in range(N)]
Y = [[] for _ in range(N)]
for i in range(N):
    X[par(i)].append(i)
    Y[par(i)].append(A[i])

ans = 0
for i in range(N):
    ans += len(set(X[i]) & set(Y[i]))

print(ans)

Submission status: Accepted

Solution code:
# D - Equals Union Find

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

# 負ならそのノードが根かつ絶対値が木の要素数を示す、正なら値のノードが根であることを示す
root = [-1] * N 

# 木の高さを示す
rank = [1] * N

# インデックスxを与えると、xの根を返す関数
def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find_root(root[x])
        return root[x]
    
# インデックスx,yを与えると、xとyの木を統合する関数
def union(x,y):
    # root_x, root_yは根のインデックス
    root_x = find_root(x)
    root_y = find_root(y)
    if root_x == root_y:
        return
    elif rank[root_x] > rank[root_y]: # 短い木(yの方)を長い木(xの方)に繋ぐ
        root[root_x] += root[root_y] # 要素数結合
        root[root_y] = root_x # 根を切り替え
    else:
        root[root_y] += root[root_x]
        root[root_x] = root_y
        
        if rank[root_x] == rank[root_y]:
            rank[root_y] += 1 # 新しい木の高さを1追加
            
for idx in range(M):
    union(xy[idx][0]-1, xy[idx][1]-1)
    
ans = 0
for i in range(N):
    if find_root(i) == find_root(p[i]-1):
        ans += 1
        
print(ans)