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

def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)

  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

def Same(x, y, par):
  return Find(x, par) == Find(y, par)

def Size(x, par):
  return -par[Find(x, par)]

n, m = map(int, input().split())
P = list(map(int, input().split()))
P = [p-1 for p in P]

par = [-1]* n
rank = [0]*n

for i in range(m):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    Unite(x, y, par, rank)

ans = 0
for i in range(n):
    if P[i] == i:
        ans += 1
    else:
        if Same(i, P[i], par):
            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):
        """要素xが属するグループの根を返す
        """
        if self.parents[x] < 0:
            return x
        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
        # 大きい方(x)に小さい方(y)をくっつけたいので、
        # 大小が逆なら入れ替える
        if self.size(x) < self.size(y):
            x, y = y, x
        # xのサイズを更新する
        self.parents[x] += self.parents[y]
        # yの親をxに変更する
        self.parents[y] = x

    def size(self, x):
        """要素xが属するグループのサイズ（要素数）を返す
        """
        return -self.parents[self.find(x)]


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

uf = UnionFind(N+1)

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

def dfs(loc,num):
    root[loc]=num
    for item in plan[loc]:
        if root[item]==-1:
            dfs(item,num)
    return 0

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

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

plan=[[]for i in range(N)]
root=[-1]*N

for _ in range(M):
    a,b=map(int,input().split())
    plan[a-1].append(b-1)
    plan[b-1].append(a-1)

for i in range(N):
    if root[i]==-1:
        dfs(i,i)

ans=0
for i in range(N):
    if root[i]==root[P[i]-1]:
        ans+=1
#print(root)
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 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):
    number = p[i]
    if uf.same(i,number-1):
      ans += 1
  print(ans)
solve()

Submission status: Accepted

Solution code:
# Union Find木の問題である

# 次のURLを参照して解いた
# http://at274.hatenablog.com/entry/2018/02/02/173000

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)
    
    # 木どうしを結合するUnionの実装
    # 木の高さをなるべく低くするために、木が低い方の根から、高い方の根に辺を張る

    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
        
            # 木の高さが同じ場合は片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


n, m = map(int, input().split())
P = list(map(int, input().split()))
XY = []
ans = 0

for _ in range(m):
    xy = list(map(int, input().split()))
    XY.append(xy)

UF = UnionFind(n)
for i in range(m):
    UF.union(P[XY[i][0]-1], P[XY[i][1]-1])

for j in range(n):
    if UF.same_check(j+1, P[j]):
        ans += 1

print(ans)

Submission status: Accepted

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

P=[i for i in range(N+1)]
S=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if S[B]<S[C]:
        P[B]=P[C]
        S[C]+=S[B]
    else:
        P[C]=P[B]
        S[B]+=S[C]
        
for i in range(M):
    x,y=map(int,input().split())
    union(x,y)
#print(P)
D={}

for i in range(1,N+1):
    D[p[i]]=i
    
#print(D2)
ans=0
for i in range(1,N+1):
    if find(i)==find(D[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(lambda z:int(z)-1,input().split()))
pre = [i for i in range(n)]
for _ in range(m):
  x,y = map(lambda z:int(z)-1,input().split())
  while pre[x] != x:
    x = pre[x]
  while pre[y] != y:
    y = pre[y]
  if x == y:
    continue
  elif x < y:
    pre[y] = x
  else:
    pre[x] = y
home1 = [10**6 for _ in range(n)]
home2 = [10**6 for _ in range(n)]
for i in range(n):
  I = i
  while pre[I] != I:
    I = pre[I]
  home1[i] = I
  home2[a[i]] = I
ans = 0
for i in range(n):
  if home1[i] == home2[i]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#16:00
n,m = map(int,input().split())
a = list(map(lambda x:int(x)-1,input().split()))
pre = [i for i in range(n)]
for _ in range(m):
  X,Y = map(int,input().split())
  X -= 1
  Y -= 1
  while pre[X] != X:
    X = pre[X]
  while pre[Y] != Y:
    Y = pre[Y]
  if X == Y:
    continue
  elif X < Y:
    pre[Y] = X
  else:
    pre[X] = Y
#print(a)
#print(pre)
region = [[] for _ in range(n)]
ser = [[] for _ in range(n)]
for i in range(n):
  b = a[i]
  I = i
  while pre[I] != I:
    I = pre[I]
  region[I].append(b)
  ser[I].append(i)
#print(region)
#print(ser)
home = [10**6 for _ in range(n)]
mother = [10**6 for _ in range(n)]
for i in range(n):
  for x in region[i]:
    home[x] = i
for i in range(n):
  for y in ser[i]:
    mother[y] = i
#print(home)
#print(mother)
ans = []
for i in range(n):
  if home[i] == mother[i]:
    ans.append(i)
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
################
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_counte():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    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)

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

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = [list(map(int,input().split())) for i in range(m)]
    un = UnionFind(n)
    for i in range(m):
        un.union(xy[i][0]-1,xy[i][1]-1)
    ans = 0
    for i in range(n):
        if un.same_group_or_no(i,p[i]-1):
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = [list(map(int,input().split())) for j in range(m)]
    un = UnionFind(n)
    for i in range(m):
        un.union(xy[i][0]-1,xy[i][1]-1)
    ans = 0
    for i in range(n):
        if un.same_group_or_no(i,p[i]-1):
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

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())
p=[0]+list(map(int,input().split()))
h=UnionFind(n+1)
ans=0
for i in range(m):
    a,b=map(int,input().split())
    h.Unite(a,b)
for i in range(1,n+1):
    if h.isSameGroup(p[i],i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        # 根は子を含む集合のデータ数を負数でもつ
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

        # y に x をつなげる
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

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

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]

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


N, M = [int(_) for _ in input().split()]
uf = UnionFind(N+10)
P = [int(_) for _ in input().split()]
for i in range(M):
    x, y = [int(_) for _ in input().split()]
    uf.merge(x, y)
cnt = 0
for i, p in enumerate(P):
    cnt += uf.same(i + 1, p)
print(cnt)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = [list(map(int,input().split())) for i in range(m)]
    un = UnionFind(n)
    ans = 0
    for i in range(m):
        un.union(xy[i][0]-1,xy[i][1]-1)
    for i in range(n):
        if un.same_group_or_no(i,p[i]-1):
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[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)]

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i: self.members(i) for i in self.address()}

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


n,m=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(m)]
UnionFind=UnionFind(n)

for x,y in XY:
    UnionFind.Unite(x-1,y-1)

print(sum([UnionFind.isSameGroup(i,j-1) for i,j in enumerate(P)]))

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)
        self.size = [1] * (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
            self.size[y] += self.size[x]
            self.size[x] = 0
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
n, m = map(int, input().split())
p = list(map(int, input().split()))
G = UnionFind(n)
for i in range(m):
    x,y = map(int, input().split())
    G.union(x,y)
ans = 0
for i in range(1,n+1):
    if G.same_check(p[i-1], i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # nはノードの数
    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]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  p=list(map(int,input().split()))
  xy=[list(map(int,input().split())) for i 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)
  uf=UnionFind(n)
  for i in range(m):
    uf.union(p[xy[i][0]-1]-1,p[xy[i][1]-1]-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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

    def unite(self, a, b):
        # set a's parent as b's parent
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 == r2:
            return
        self.parent[r2] = r1

    def root(self, a):
        if self.parent[a] == a:
            return a
        par = self.root(self.parent[a])
        self.parent[a] = par
        return par

    def sameRoot(self, a, b):
        return self.root(a) == self.root(b)

    def reroot(self):
        for ix, a in enumerate(self.parent):
            self.parent[ix] = self.root(a)
        return

def main():
    N, M = LI()
    P = LI_()
    X, Y = [], []
    uf = UnionFind(N)
    for _ in range(M):
        x, y = LI_()
        uf.unite(x, y)
    cnt = 0
    for ix, p in enumerate(P):
        if uf.sameRoot(ix, P[ix]):
            cnt += 1
    print(cnt)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

    def unite(self, a, b):
        # set a's parent as b's parent
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 == r2:
            return
        self.parent[r2] = r1

    def root(self, a):
        if self.parent[a] == a:
            return a
        par = self.root(self.parent[a])
        self.parent[a] = par
        return par

    def reroot(self):
        for ix, a in enumerate(self.parent):
            self.parent[ix] = self.root(a)
        return

def main():
    N, M = LI()
    P = LI_()
    X, Y = [], []
    uf = UnionFind(N)
    for _ in range(M):
        x, y = LI_()
        uf.unite(x, y)
    uf.reroot()
    groups = collections.defaultdict(set)
    for i, par in enumerate(uf.parent):
        groups[par].add(i)

    cnt = 0
    for _, g in groups.items():
        for ix in g:
            if P[ix] in g:
                cnt += 1
    print(cnt)
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
        indlist = set([p[i] for i in numlist])
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)

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()))
s = [list(map(int, input().split())) for i in range(m)]

uf = UnionFind(n)
for x, y in s:
    uf.union(x-1, y-1)

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