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:
n,m = map(int,input().split())
p_list = list(map(int,input().split()))
x_y_list = []
for i in range(m):
  x_y_list.append(list(map(int,input().split())))
  
class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
U = UnionFindPathCompression(n)

for x_y in x_y_list:
  x = x_y[0] -1
  y = x_y[1] - 1
  U.union(x,y)
  
count = 0
for i in range(n):
  if U.same(i,p_list[i]-1) == True:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc097/tasks/arc097_b
# 15:36-15:48 give up => hint
# 15:53-16:16　RE(recursion overflow)
# 16:16-16:43 done


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    p = [num-1 for num in p]
    x, y = [None] * M, [None] * M
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1  # 0-index
        y[i] -= 1  # 0-index

    edges = {node: [] for node in range(N)}
    for xi, yi in zip(x, y):
        edges[xi].append(yi)
        edges[yi].append(xi)

    ans = 0
    check_node = [None] * N
    for start in range(N):
        if check_node[start] is not None:
            continue

        indexes = []
        numbers = []
        queue = [start]
        queue_i = 0
        while queue_i < len(queue):
            node = queue[queue_i]
            if check_node[node] is not None:
                queue_i += 1
                continue

            check_node[node] = 1
            indexes.append(node)
            numbers.append(p[node])
            
            for edge in edges[node]:
                if check_node[edge] is None:
                    queue.append(edge)
            
            queue_i += 1

        ans += len(set(indexes) & set(numbers))

    return ans


print(main())

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
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 main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M = LMIIS()
    tree = UnionFind(N)
    P = LMIIS()
    for i in range(M):
        x,y = LMIIS()
        tree.union(x-1,y-1)
    ans = 0
    for i in range(N):
        if i+1 == P[i] or tree.find(i) == tree.find(P[i]-1):
            ans += 1
    print(ans)



    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
      
n,m = map(int,input().split())
P = list(map(int,input().split()))

uf = UnionFind(n)

for i in range(m):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]
    
    def find(self,x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x,y =y,x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def same(self,x,y):
        return self.find(x) == self.find(y)

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

    def is_roota(self,x):
        return self.parent[x] < 0

n,m =map(int, input().split())
p = list(map(int, input().split()))
count = 0
pair_list = []
for i in range(m):
    array = list(map(int,input().split()))
    array[0] -= 1
    array[1] -= 1  # リストの添字にあわせるため
    pair_list.append(array)

uf = UnionFind(len(p))  # unionfind作成

# 整数のペア(x,y)を同じグループに結合
for i in range(m):
    uf.unite(pair_list[i][0], pair_list[i][1])

# 経路圧縮を行い、親要素をすべて根に更新する
for i in range(n):
    uf.find(i)

# 順列pに含まれる要素p[i]の値とindex+1が一致していたらcount
# p[i]の本来いて欲しいindex(ex. p[i] = 5なら５番目に並んで欲しいから4)と
# p[i]が移動したいindexにいるp[i]のindex+1
# (ex. 5番目にいる値のufにおけるindex 5番目に２がいたら２−１＝１みたいな
for i in range(n):
    if p[i] == i+1:
        count += 1
    else:
        if uf.same(p[i]-1, p[p[i]-1]-1) is True:
            count += 1
        else:
            continue
print(count)

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n_nodes):
        # 親要素のノード番号を格納する.
        # self.parent[x] == x の時，そのノードは根.
        self.parent = [i for i in range(n_nodes)]

        # 木の高さを格納する．
        self.rank = [0] * n_nodes

    # 検索. 根を返す.
    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[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # 同じ集合に属するか判定
    def check(self, x, y):
        return self.find(x) == self.find(y)


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

tree = UnionFind(N)

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

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    p=list(map(int1,input().split()))
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    
    u=UnionFind(N)
    for _ in range(M):
        x,y=map(int1,input().split())
        u.unite(x,y)
    ans=0
    for i in range(N):
        if u.is_same(i,p[i]):
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

l1 = [[] for i in range(n)]
l2 = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    l1[x].append(i)
    l2[x].append(l[i]-1)
ans = 0
for i in range(n):
    a = set(l1[i])
    b = set(l2[i])
    ans += len(a&b)
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 _ in range(m)]

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

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

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

            if x == y:
                return

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

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

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

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

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

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

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return_list = [list() for i in range(n)]
            for i in range(n):
              return_list[self.find(i)].append(i)
            return return_list

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    uf = UnionFind(n)
    ans = 0
    for x,y in xy:
        uf.union(x-1,y-1)
    for v in uf.all_group_members():
        set1 = set()
        for i in v:
            set1.add(p[i]-1)
        ans += len(set(v)&set1)

    print(ans)

if __name__ == '__main__':
    main()

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 _ in range(m)]

    class UnionFind(object):
        def __init__(self, n=1):
            self.par = [i for i in range(n)]
            self.rank = [0 for _ in range(n)]
            self.size = [1 for _ in range(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:
                if self.rank[x] < self.rank[y]:
                    x, y = y, x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                self.par[y] = x
                self.size[x] += self.size[y]

        def all_group_members(self):
            return_list = [list() for i in range(n)]
            for i in range(n):
              return_list[self.find(i)].append(i)
            return return_list

    uf = UnionFind(n)
    ans = 0
    for x,y in xy:
        uf.union(x-1,y-1)
    for v in uf.all_group_members():
        set1 = set()
        for i in v:
            set1.add(p[i]-1)
        ans += len(set(v)&set1)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]

uf=UnionFind(2*n)
for i in range(n):
    uf.merge(i,p[i]+n-1)
for i in range(m):
    x,y=map(int,input().split())
    x-=1;y-=1
    uf.merge(x,y)
ans=0
for i in range(n):
    ans+=int(uf.issame(i,i+n))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
p = list(map(int, input().split()))
p_inv = [0]*(N+1)
for i in range(1, N+1):
    p_inv[p[i-1]] = i

graph = [[] for _ in range(N+1)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

stack = deque()
is_checked = [0] * (N+1)
links = [[] for _ in range(N+1)]
for i in range(1, N+1):
    stack.append(i)
    while stack:
        node = stack.pop()
        if is_checked[node]:
            continue

        links[i].append(node)
        for next in graph[node]:
            stack.append(next)

        is_checked[node] = 1

ans = 0
for l in links:
    check = set()
    for num in l:
        check.add(p_inv[num])
    l = set(l)
    ans += len(l & check)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
p=list(map(int,input().split()))
fromto=[]
tree=[[] for _ in range(N)]
for i in range(N):
    fromto.append([i,p[i]-1])
cnt=0
for i in range(M):
    x,y=map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
col=[-1]*N
for i in range(N):
    if col[i]==-1:
        d = deque()
        d.append(i)
        while len(d)>0:
            v=d.popleft()
            col[v]=i
            for j in tree[v]:
                if col[j]==-1:
                    d.append(j)
            #print(col,d)
            #input()
#print(col,fromto)
for i in range(N):
    x=fromto[i][0]
    y=fromto[i][1]
    if col[x]==col[y]:
        cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    
    def all_group_members(self):
        return_list = [list() for i in range(n)]
        for i in range(n):
          return_list[self.find(i)].append(i)
        return return_list
      
      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
xy = [list(map(int, input().split())) for i in range(m)]
for x,y in xy:
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a:
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.siz = [1] * n
    
    def root(self, x):
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        if rx != ry:
            if self.siz[rx] < self.siz[ry]: 
                rx, ry = ry, rx
            self.par[ry] = rx
            self.siz[rx] += self.siz[ry]
    
    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)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    pars = list(range(N))

    def getpar(n: int):
        if pars[n] == n:
            return n
        pars[n] = getpar(pars[n])
        return pars[n]

    def union(a: int, b: int):
        pars[getpar(a)] = getpar(b)

    for xi, yi in zip(x, y):
        union(xi - 1, yi - 1)
    print(sum(
        1
        for i in range(N)
        if getpar(p[i] - 1) == getpar(i)
    ))


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:
nim, M = map(int, input().split())
ps = list(map(int, input().split()))
G = list(range(nim))
def getparent(n):
  if G[n] == n:
    return n
  G[n] = getparent(G[n])
  return G[n]
for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  x = getparent(x)
  y = getparent(y)
  G[x] = y
Ss = [set() for i in range(nim)]
for i in range(nim):
  j = getparent(i)
  Ss[j].add(ps[i])
r = 0
for i in range(nim):
  if i+1 in Ss[G[i]]:
    r += 1
print(r)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)
    
    par = [-1]*n

    for x, y in xy:
        if same(x-1, y-1) == False:
            unite(x-1, y-1)
    res = 0
    for i in range(n):
        if i == p[i]-1:
            res += 1
        else:
            if same(i, p[i]-1):
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def LIR_(n): return [LI_() for i in range(n)]
def D():
    n, m = LI()
    p = LI_()
    xy = LIR_(m)
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1
 
    for x,y in xy:
        union(x, y)
    ans = 0
    for i in range(n):
        if find(p[i]) == find(i):
            ans += 1
    
    print(ans)
D()

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 6)


class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

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

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    U = UnionFind(N)
    for i in range(M):
        U.union(x[i] - 1, y[i] - 1)
    sum = 0
    for i in range(N):
        if p[i] == i + 1 or U.same(p[i] - 1, i):
            sum += 1
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
N, M = map(int,input().split())
P = list(map(int,input().split()))

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def 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]

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

ans = 0

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

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

edge = np.array([tuple(map(int1, input().split())) for _ in range(M)]).T
matr = csr_matrix((np.ones(M, dtype="int64"), edge), (N, N))

C, labels = connected_components(matr)
lst = [[set(), set()] for _ in range(C)]
for i, x in enumerate(labels):
    lst[x][0].add(i)
    lst[x][1].add(P[i])

for c in range(C):
    lst[c] = lst[c][0] & lst[c][1]
print(sum(len(s) for s in lst))

Submission status: Accepted

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

#Union-find
U=[i for i in range(N+1)] #根の頂点

#根を与える関数
def root(x):
    global U
    if x==U[x]:
        return x
    else:
        U[x]=root(U[x])  #経路圧縮
        return U[x]

#併合関数
def unite(x,y):
    global U
    if root(x)!=root(y):
        U[root(x)]=root(y)

#判定関数
def same(x,y):
    global U
    if root(x)==root(y):
        return 1
    else:
        return 0

for j in range(M):
    X,Y=map(int,input().split())
    unite(X,Y)

ans=0
for k in range(1,N+1):
    ans+=same(k,P[k])

print(ans)

Submission status: Accepted

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

# union-Find##
par = [-1] * (n + 1)


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


def unite(x, y):
    a = root(x)
    b = root(y)
    if a == b:
        return False
    else:
        if par[a] > par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


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


def size(x):
    return -par[root(x)]


# union-find##

for _ in range(m):
    x, y = map(int, input().split())
    unite(x, y)

cnt = 0
for i in range(n):
    if is_same(P[i], i + 1):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)
chk = [[set(),set()] for i in range(n)]
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
      
def same(x,y):
    return find(x) == find(y)
  
par = [-1]*n
ans = 0
for i in range(m):
  x,y = [int(i) for i in input().split()]
  unite(x-1,y-1)

for i,pi in enumerate(p):
  if same(i,pi-1):
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)
chk = [[set(),set()] for i in range(n)]
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
      
par = [-1]*n
ans = 0
for i in range(m):
  x,y = [int(i) for i in input().split()]
  unite(x-1,y-1)

for i in range(n):
  m = find(i)
  chk[m][0].add(p[i])
  chk[m][1].add(i+1)

for i in range(n):
  ans += len(chk[i][0] & chk[i][1])
    
print(ans)