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 collections
import sys


class unionFind:
    parent = []

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

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

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

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


input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(M)]
ans = 0
t = unionFind(N)

for x, y in xy:
    t.unite(x, y)

for i in range(N):
    if t.same(i+1, p[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, 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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
t = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = [int(i) for i in input().split()]
    t[x].append(y)
    t[y].append(x)
l = [0]*(N+1)
stack = []
seen = [False]*(N+1)
c = 1
for i in range(1, N+1):
    if not seen[i]:
        stack.append(i)
        seen[i] = True
        c = i
    while len(stack):
        n = stack.pop()
        l[n] = c
        for v in t[n]:
            if not seen[v]:
                stack.append(v)
                seen[v] = True
ans = 0
for i, n in enumerate(p):
    if l[i+1] == l[n]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    n, m = map(int, input().split())
    p = tuple(map(int, input().split()))
    uf = UF_tree(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x, y)

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

    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()))
XY = [list(map(int, input().split())) for _ in range(M)]

uf = UnionFind(N)
for xy in XY:
  x, y = xy                       
  uf.union(x - 1, y - 1)
                         
ans = 0
for itr, val in enumerate(P):
  if itr == val - 1 or uf.same(itr, val - 1):
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
P = rl()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N+1)]
for i in range(M):
    x, y = rl()
    if find(V, x) != find(V, y):
        union(V, x, y)
index_set = [set() for _ in range(N+1)]
p_set = [set() for _ in range(N+1)]
answer = 0
for i in range(1, N+1):
    root = find(V, i)
    index_set[root].add(i)
    p_set[root].add(P[i-1])

for i in range(1, N+1):
    answer += len(index_set[i] & p_set[i])
print(answer)
# 長時間経過

Submission status: Accepted

Solution code:
# 参考URL
# https://note.nkmk.me/python-union-find/
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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


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)

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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, x):
    self.x=x
    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
    elif self.rnk[x]>self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x]==self.rnk[y]:
        self.rnk[y]+=1
  
  def isSameGroup(self, x, y):
    return self.Find_root(x)==self.Find_root(y)
  
  def Count(self, x):
    return -self.root[self.Find_root(x)]

N,M = map(int,input().split())
p = list(map(lambda x : int(x)-1,input().split()))
count = 0
uf = UnionFind(N)
for _ in range(M):
    i,j = map(lambda x : int(x)-1,input().split())
    uf.Unite(i,j)
for i in range(N):
    if uf.isSameGroup(p[i],i):
        count += 1
print(count)

Submission status: Accepted

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

root = list(range(1, N+1))


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


for _ in range(M):
    x, y = map(int, input().split())
    x = find(x)
    y = find(y)
    root[max(x, y) - 1] = min(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:
N,M=map(int,input().split())
P=list(map(int,input().split()))
  
root=list(range(1,N+1))

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

for _ in range(M):
  x,y=map(int,input().split())
  x=find(x)
  y=find(y)
  if x!=y:
    root[max(x,y)-1]=min(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 collections import deque

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())
P = [val-1 for val in map(int,input().split())]
ans = 0
uf = UnionFind(N)

for _ in range(M):
  x,y = map(int,input().split())
  if uf.same_check(x-1,y-1) is False:
    uf.union(x-1,y-1)

for i in range(N):
  if uf.same_check(i,P[i]):
    ans += 1
print(ans)

Submission status: Accepted

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

class UnionFind():
  def __init__(self, x):
    self.x=x
    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
    elif self.rnk[x]>self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x]==self.rnk[y]:
        self.rnk[y]+=1
  
  def isSameGroup(self, x, y):
    return self.Find_root(x)==self.Find_root(y)
  
  def Count(self, x):
    return -self.root[self.Find_root(x)]

u=UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  u.Unite(x,y)
ans=0
for i in range(N):
  if u.isSameGroup(i+1,p[i]):
    ans+=1
  else:
    continue
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue,copy
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g
 
def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
def unite(x,y): # 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): # xとyが同じ集合に属するか判定
    return find(x)==find(y)
 
def main():
    n,m=inpm()
    global par,rank
    par=[i for i in range(n)]  # 親
    rank=[0 for _ in range(n)] # 木の深さ
    p=inpl()
    xy=[]
    for _ in range(m):
        x,y = inpm()
        if x>y:
            x,y=y,x
        xy.append([x,y])
    xy.sort()
    for i in range(m):
        x,y=xy[i]
        unite(x-1,y-1)
    groop=[[] for _ in range(n)]
    for i in range(n):
        groop[find(i)].append(i)
    ans=0
    for i in range(n):
        ps=[]
        for j in range(len(groop[i])):
            ps.append(p[groop[i][j]]-1)
        if ps==[]:
            continue
        else:
            ans+=len(set(ps)&set(groop[i]))
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

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

    # Union-Find木
    class UnionFind():
        def __init__(self, n):
            self.tree = [i for i in range(n)]

        def root(self, x):
            if(self.tree[x] == x):
                return x
            self.tree[x] = self.root(self.tree[x])
            return self.tree[x]  # 経路圧縮

        def same(self, x, y):  # xとyが同じ木に属するか
            return self.root(x) == self.root(y)

        def unite(self, x, y):
            x = self.root(x)
            y = self.root(y)
            if(x == y):
                return
            self.tree[x] = y

    uf = UnionFind(n)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
p = LIST()
xy = [LIST() for _ in range(M)]

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)

tree = UnionFind(N)

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

ans = 0
for i in range(N):
	if i+1 == p[i]:
		ans += 1
	elif tree.same_check(i+1, p[i]):
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        par[x] = y

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def main():
    N, M = map(int, readline().split())
    p = list(map(int, readline().split()))
    m = map(int, read().split())
    XY = list(zip(m, m))

    par = list(range(N))
    rank = [0] * N

    for x, y in XY:
        x -= 1
        y -= 1
        unite(rank, par, x, y)

    d_p = defaultdict(list)
    d_index = defaultdict(list)
    for i in range(N):
        par[i] = root(par, i)
        d_index[par[i]].append(p[i])
        d_p[par[i]].append(i+1)

    cnt = 0
    for i in set(par):
        cnt += len(list(set(d_index[i]) & set(d_p[i])))

    print(cnt)


main()

Submission status: Accepted

Solution code:
#D
N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = [list(map(int,input().split())) for i in range(M)]

#UnionFind
class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n #root[x]<0 ならxが根かつその値が木の要素数
        self.rank = [0]*n #木の深さ
    def __del__(self):
        pass
        
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[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.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[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) #bool
    
    def count(self,x):
        return -self.root[self.find(x)]
    
uf = UF(N)
for xy in XY:
    x,y = xy
    uf.unite(x-1,y-1)
    
ans = 0
for i,p in enumerate(P):
    if uf.same(p-1,i):
        ans+=1
        
print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

uf = UnionFind(N)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush,heappop
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,m = (int(i) for i in input().split())
  p = list(int(i) for i in input().split())

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

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

def func(x):
    return x - 1

def main():
    N, M = map(int, input().split())
    P = list(map(func, map(int, input().split())))
    uni = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        uni.union(x, y)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heapify,heappop,heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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]

n,m = inpl()
p = inpl()
uf = UnionFind(n)
for i in range(m):
    a,b = inpl()
    uf.union(a-1,b-1)
res = 0
for i in range(n):
    if uf.find(p[i]-1) == uf.find(i):
        res += 1
print(res)

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())
x=UnionFind(n)
lists=list(map(int,input().split()))          
for i in range(m):
    a,b=map(int,input().split())
    x.union(a,b)
uselist=[0]*n
for i in range(1,n+1): 
    uselist[i-1]=x.find(i)
grouplist=[[]for i in range(n+1)]
sublist=[[]for i in range(n+1)]
for i in range(n):
    grouplist[uselist[i]].append(lists[i])
    sublist[uselist[i]].append(i+1)
ans=0
for i in range(n+1):
    x=set(grouplist[i]) & set(sublist[i])
    ans+=len(x)
print(ans)

Submission status: Accepted

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

def find(a,root):
    if root[a] == a:
        return a
    else:
        root[a] = find(root[a],root)
        return root[a]

def unite(a,b,root,depth):
    A = find(a,root)
    B = find(b,root)
    if A == B:
        return
    elif depth[A] > depth[B]:
        root[B] = A
        depth[A] += depth[B]
    else:
        root[A] = B
        depth[B] += depth[A]
for i in range(M):
    x,y = map(int,input().split())
    unite(x-1,y-1,root,depth)

order = [-1 for _ in range(N)]
for i in range(N):
    order[p[i]-1] = find(i,root)
count = 0
for i in range(N):
    if order[i] == root[i]:
        count += 1
print(count)

Submission status: Accepted

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

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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

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

ope = UnionFind(N)

for i in range(M):
	ope.Unite(O[i][0], O[i][1])

cnt = 0

for i in range(N):
	if ope.isSameGroup(i+1, A[i]):
		cnt += 1

print(cnt)

Submission status: Accepted

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

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
 
#(方針)　(x,y)をunion-findにいれて, P[i]とiの根が同じならスワップできる
N,M = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N): 
  P[i] = P[i]-1
  
union = UnionFind(N)
for i in range(M):
  x,y = map(int,input().split())
  union.Unite(x-1,y-1)

ans = 0
for i in range(N):
  if(union.isSameGroup(P[i],i) == True): ans += 1 
print(ans)