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:
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)]
pos = [0] * (N + 1)
for i in range(N):
  pos[P[i]] = i
#print(pos)
uf = UnionFind(N)
for i in range(M):
  uf.union(XY[i][0]-1,XY[i][1]-1)
#print(uf)
ans = 0
for i in range(N):
  if uf.same(i,pos[i+1]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from itertools import groupby
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
p = list(map(int, readline().split()))
xy = map(int, read().split())


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


tree = UnionFind(N)
for x, y in zip(xy, xy):
    tree.Unite(x, y)

group = tree.root[1:]
number = list(range(1, N + 1))
answer = 0

for i in range(N):
    if tree.isSameGroup(number[i], p[i]):
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import sys


#https://note.nkmk.me/python-union-find/
class AlgUnionFind():
    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():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    p = list(map(int, input().rstrip('\n').split()))
    uf = AlgUnionFind(n)
    for i in range(m):
        x, y = list(map(int, input().rstrip('\n').split()))
        uf.union(x-1, y-1)
    for i in range(n):
        p[i] = [p[i]-1, p[i]-1 == i]
    while True:
        c_sw = False
        for i in range(len(p)):
            tn = p[i][0]
            if not p[i][1] and not p[tn][1]:
                if uf.same(tn, p[tn][0]):
                    p[tn][0], p[i][0] = p[i][0], p[tn][0]
                    p[i][1] = p[i][0] == i
                    p[tn][1] = p[tn][0] == tn
                    c_sw = True
        if not c_sw:
            break
    cnt = 0
    for i in range(n):
        cnt += p[i][1]
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind:
  def __init__(self,nodes):
    self.parents={node: node for node in nodes}
  def root(self,x):
    if x==self.parents[x]:
      return x
    else:
      rt=self.root(self.parents[x])
      self.parents[x]=rt
      return rt
  def find(self,x,y):
    return self.root(x)==self.root(y)
  def union(self,x,y):
    self.parents[self.root(x)]=self.root(y)

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

inf=float("inf")
n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

uf=WeightedUnionFind(n+1)
cnt=0
for i in range(m):
    uf.union(xy[i][0],xy[i][1],0)
for i in range(n):
    if uf.same(i+1,p[i]):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
xs=[tuple(map(int,input().split())) for _ in range(m)]
def root(n):
  if union[n]==n:
    return n
  union[n]=root(union[n])
  return union[n]
union={x:x for x in range(1,n+1)}
for x,y in xs:
  union[root(x)]=root(y) 
print(sum(root(i+1)==root(p[i]) for i in range(n)))

Submission status: Accepted

Solution code:
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n,q=map(int,input().split())
size=[1]*n
ans=0 
l=[int(i) for i in input().split()]
parent=[i for i in range(n)]
for i in range(q):
    a,b=map(int,input().split())
    parent,size=union(parent,size,a-1,b-1)
for i in range(n):
    if find(parent,i)==find(parent,l[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())

def main():
    n,m=map(int,input().split())
    p = list(map(int,input().split()))
    uf = UnionFind(n)
    res = 0
    for _ in range(m):
        x,y=map(int,input().split())
        uf.union(x-1,y-1)
    for i in range(n):
        if uf.same(p[i]-1,i):
            res += 1
    print(res)

main()

Submission status: Accepted

Solution code:
from collections import deque

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

out=[set() for i in range(N+1)]

for k in range(M):
    x,y=map(int,input().split())
    out[x].add(y)
    out[y].add(x)

rch=[False for i in range(N+1)]
ans=0
q=deque()
for i in range(1,N+1):
    if not rch[i]:
        si=set()            
        q.append(i)
        rch[i]=True
        si.add(i)
        while q:
            u=q.popleft()
            for v in out[u]:
                if not rch[v]:
                    q.append(v)
                    rch[v]=True
                    si.add(v)
        sv={p[i-1] for i in si}
        ans+=len(si&sv)
              
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        """ あるノードの属する集合のノード数 """
        return self.size[self.find(x)]
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N, M = MAP()
P = [p-1 for p in LIST()]

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

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

Submission status: Accepted

Solution code:
#Equals
n,m=map(int,input().split())
p=list(map(int,input().split()))
p=[0]+p
data=[[] for _ in range(n+1)]
flag=[0]*(n+1)
for i in range(m):
    x,y=map(int,input().split())
    data[x].append(y)
    data[y].append(x)
tree=[0]*(n+1)
for i in range(1,n+1):
    if flag[i]==0:
        que=[i]
    while que:
        h=que.pop()
        flag[h]=1
        tree[h]=i
        for u in data[h]:
            if flag[u]==0:
                que.append(u)
count=0
for i in range(1,n+1):
    if tree[i]==tree[p[i]]:
        count+=1
print(count)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, data):
        self.parent = {}
        self.rank = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.rank[i] = 0
 
    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 same(self, x, y):
        return self.find(x) == self.find(y)
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.find(x) == self.find(y):
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            return
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]: self.rank[y] += 1
            return

N, M = map(int, input().split())
P = list(map(int, input().split()))
L = []
for i in range(M):
    L.append([int(x) for x in input().split()])
tree = UnionFind(N)
for i in range(M):
    tree.unite(P[L[i][0]-1], P[L[i][1]-1])
ans = 0
for i in range(N):
    if tree.same(P[i], i+1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, data):
        self.parent = {}
        self.rank = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.rank[i] = 0

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


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


N, M = map(int, input().split())
P = list(map(int, input().split()))
L = []
for i in range(M):
    L.append([int(x) for x in input().split()])

tree = UnionFind(N)
for i in range(M):
    tree.unite(P[L[i][0]-1], P[L[i][1]-1])

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        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 = [int(p) for p in input().split()]
L = []
for i in range(M):
    L.append([int(x) for x in input().split()])
    
tree = UnionFind(N)
for i in range(M):
    tree.unite(P[L[i][0]-1], P[L[i][1]-1])
    
ans = 0
for i in range(N):
    if tree.isSameGroup(P[i], i+1):
        ans += 1
        
print(ans)

Submission status: Accepted

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

a={i:i for i in range(n)}

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

for x,y in s:
    a[find(x)] = find(y)

ans=0

for i in range(n):
    if find(i)==find(p[i]):
        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 same(self, x, y):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
Permutation = list(map(int,input().split()))
Replace = [list(map(int,input().split())) for i in range(m)]

uf = UnionFind(n+1)
count = 0

for i in range(m):
    uf.union(Replace[i][0],Replace[i][1])

for i in range(1,n+1):
    if uf.same(Permutation[i-1],i):
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]

v = [[] for _ in range(N)]
for _ in range(M) :
    x, y = map(int, input().split())
    v[x-1].append(y-1)
    v[y-1].append(x-1)
    
ret = 0
visited = [False] * N
for i in range(N) :
    if visited[i] :
        continue
    
    q = [i]
    visited[i] = True
    a = [i+1]
    b = [p[i]]
    
    while q :
        cur = q.pop()
        for nex in v[cur] :
            if visited[nex] :
                continue
            q.append(nex)
            a.append(nex+1)
            b.append(p[nex])
            visited[nex] = True
    ret += len(set(a) & set(b))
print(ret)

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 = [int(x) for x in input().split()]
uf = UnionFind(N)
p = [int(x) for x in input().split()]
for _ in range(M):
  x,y = [int(x) for x in input().split()]
  uf.union(x-1,y-1)
ans = 0
for i in range(N):
  if i+1!=p[i] and uf.same(i,p[i]-1):
    ans +=1
  elif i+1==p[i]:
    ans += 1
print(ans)

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

def main():
    n,m = map(int,input().split())
    p = [int(x) for x in input().split()]
    uni = UnionFind(n)
    for i in range(m):
        a,b = map(int,input().split())
        uni.Unite(a,b)
    cnt = 0
    for i,p_ in enumerate(p):
        if uni.isSameGroup(i+1,p_):
            cnt += 1
    print(cnt)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
  
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def 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
    else:
      self.par[y] = x
      if self.rank[x]==self.rank[y]:
        self.rank[x] += 1
  
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N, M = map(int, input().split())
h = [int(i)-1 for i in input().split()]
dic1 = defaultdict(list)
dic2 = defaultdict(list)
u = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  u.unite(a-1,b-1)

for c in range(N):
  p = u.find(c)
  dic1[p] += [c]
  dic2[p] += [h[c]]
ans = 0
for p in dic1.keys():
  dic1[p].sort()
  dic2[p].sort()
  i = 0
  j = 0
  while i<len(dic1[p]) and j<len(dic2[p]):
    if dic1[p][i]==dic2[p][j]:
      i += 1
      j += 1
      ans += 1
    elif dic1[p][i]<dic2[p][j]:
      i += 1
    else:
      j += 1
    
print(ans)

Submission status: Accepted

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

	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 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y) or x==y
		
def solve():
	n,_,*l=map(int,open(0).read().split())
	p=l[:n];xy=l[n:]
	ids=[0]*(n+1)
	for i,x in enumerate(p):ids[x]=i+1
	uf=UnionFind(n)
	for x,y in zip(*[iter(xy)]*2):uf.unite(x,y)
	print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
	
if __name__=="__main__":solve()

Submission status: Accepted

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

	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 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y) or x==y
		
def solve():
	n,m,*l=map(int,open(0).read().split())
	p=l[:n];xy=l[n:]
	ids=[0]*(n+1)
	for i in range(n):ids[p[i]]=i+1
	uf=UnionFind(n)
	for x,y in zip(*[iter(xy)]*2):uf.unite(x,y)
	print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
	
if __name__=="__main__":solve()

Submission status: Accepted

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

	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 0
		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 isSame(self, x, y):
		return self.find(x) == self.find(y)
		
n,m,*l=map(int,open(0).read().split())
p=l[:n];xy=l[n:]
ids=[0]*(n+1)
for i in range(n):
	ids[p[i]]=i+1
uf=UnionFind(n)
for x,y in zip(*[iter(xy)]*2):
	uf.unite(x,y)
print(sum(uf.isSame(i,ids[i])or i==ids[i] for i in range(1,n+1)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
nums = list(map(int, input().split()))
ids = [0] * (N+1)
for i, n in enumerate(nums):
  ids[n] = i+1

class UnionFind():
  
  def __init__(self, n):
    self.par = list(range(n+1))
    self.rank = [0] * (n+1)

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

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

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

i_tree = UnionFind(N)
  
for _ in range(M):
  x, y = map(int, input().split())
  i_tree.unite(x, y)
cnt = 0
for i in range(1, N+1):
  if i_tree.same(i, ids[i]):
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

class UF(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):
        '''
        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 と 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 is_same(self, x, y):
        '''
        x と y が同じグループか否か
        '''
        return self.find(x) == self.find(y)

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = II()
p = III()
p = list(map(lambda x:x-1, p))
x,y = Line(M)

place = [0]*N
for i in range(N):
    place[p[i]] = i

uf = UF(N)
for i in range(M):
    uf.union(x[i]-1, y[i]-1)

ans = 0
for i in range(N):
    if uf.is_same(i,place[i]):
        ans += 1

print(ans)