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(map(int,input().split()))


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

    def root(self, x): #連結している木の頂点
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y): #根が同じか判定する
        return self.root(x) == self.root(y)

    def unite(self, x, y): #くっつける
        u = self.root(x)
        v = self.root(y)

        if u == v: return

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

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

    def count(self, x): #連結成分数
        return self.size[self.root(x)]

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

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

print(ans)

Submission status: Accepted

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

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

num=[i for i in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    unite(num[x-1],num[y-1])

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

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.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
#uf = UnionFind(n) #初期化
#uf.union(0, 2)#グループを併合
#uf.find(0) #親要素が変える

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

print(cnt)

Submission status: Accepted

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


tree=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque

groups=[]
been=[0]*n
for i in range(n):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

ans=0
for group in groups:
    ans+= len( set(group) & set(p[g] for g in group) )

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

def solve():
    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())
        x -= 1
        y -= 1
        uf.unite(x,y)
    
    ans = 0
    for i in range(N):
        if uf.isSame(p[i]-1,i):
            ans += 1
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes

        # self.parents[x] < 0 の時，xが根である．
        # また，xが根の時，(-1) * (同一グループの要素数) が格納されるようになる.
        self.parents = [-1] * n_nodes

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

        if x == y:
            return

        # 常にxの方が要素数が多くなるように，スワップする
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        # 要素数の少ない方のグループを，要素数が多い方の木に貼る．
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

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

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

par = [i for i in range(n)]
rank = [0]*n

def UnionFind(n):
    if par[n] == n:
        return n

    parent = par[n]
    par[n] = UnionFind(parent)
    return par[n]


def Unite(left, right):
    rootLeft = UnionFind(left)
    rootRight = UnionFind(right)
    if rootLeft != rootRight:
        if rank[rootRight] < rank[rootLeft]:
            par[rootRight] = rootLeft
        else:
            par[rootLeft] = rootRight
            if rank[rootLeft] == rank[rootRight]:
                rank[rootLeft] += 1



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

sum = 0
for i, p in enumerate(ps):
    sourceRoot = UnionFind(i)
    targetRoot = UnionFind(p - 1)
    if sourceRoot == targetRoot:
       sum += 1

print(sum)

Submission status: Accepted

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

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

root = [[] for i in range(n)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)

check = [-1]*n

ans = 0

for j in range(n):
    if check[j] != -1:
        continue
    stack=[j]
    check[j]=j
    while len(stack):
        v = stack.pop(0)
        for i in root[v]:
            if check[i] == -1:
                check[i]=j
                stack.append(i)
for k in range(n):
    if check[k] == check[p[k]-1] :
        ans += 1

print(ans)

Submission status: Accepted

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

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

unionfind = UnionFind(N + 1)

for _ in range(M):
    x, y = map(int, input().split())
    unionfind.union(P[x - 1], P[y - 1])

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_members(self, x):  # x が属する集合の要素を返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  # print 表示用
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())


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

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

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

print(ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]  # parent. if par[x]==x: x is root.
        self.rank = [0 for i in range(n)]  # depth of tree

    def find(self, x):  # find root
        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)

    def is_root(self, x):
        return self.par[x] == x

    def roots(self):
        return [i for i in range(self.n) if self.is_root(i)]

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

    def groups(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    p = list(map(lambda x: x - 1, p))

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

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

    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():
    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())
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)
ans = 0
for i in range(n):
    if uf.find(i) == uf.find(p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

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

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]


for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        0
        #print(par[1:])
    else:
        par[root(y)]=root(x)
        #print(par[1:])

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]):
        ans=ans+1
print(ans)
'''
print(par[1:])

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''

Submission status: Accepted

Solution code:
def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_check(root,x,y):
    if find_root(root,x) == find_root(root,y):
        return True
    else:
        return False
    
def UF_make(graph,n):  #グラフと最大項を与えると、塊ごとにグルーピングする
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):  #これを入れれば、UF_checkを使わずに一塊になる
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

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

UF=UF_make(XY,N)
#print(UF)

groups=[[] for i in range(N+1)]
for i in range(N):
    groups[UF[i]].append(P[i])

for i in range(N+1):
    groups[i].sort()

import bisect
ans=0
for i in range(N):
    num=bisect.bisect_left(groups[UF[i]],i+1)
    if num!=len(groups[UF[i]]) and groups[UF[i]][num]==i+1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
P = tuple(map(lambda n: int(n) - 1, input().split()))
row, column = zip(*tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M)))
matrix = csr_matrix((np.ones((M,), dtype=np.int8), (row, column)), dtype=np.int8, shape=(N, N))
connection = csgraph.connected_components(matrix)[1]
print(sum(len(set(connection[list(pair)])) == 1 for pair in enumerate(P)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #xの属するグループの要素一覧
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self): #グループ個数
        return len(self.roots())

    def all_group_members(self): #根とその要素の辞書配列
        return {r: self.members(r) for r in self.roots()}

    def __str__(self): #print用
        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()))
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(P[i]-1,i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

def main():
  global N 
  N, M = map(int, input().split())
  global par 
  par = [-1] * N
  p = list(map(int, input().split()))
  for i in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)
  ans = 0
  for i in range(N):
    if same(i, p[i]-1):
      ans += 1
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
p = LI()
xy = []
for i in range(M):
    x, y = LI()
    x -= 1
    y -= 1
    xy.append((x, y))

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

uf = UnionFind(N)
p_dic = {}
for i in range(N):
    p_dic[p[i]] = i
# print(p_dic)

for i in range(M):
    x, y = xy[i]
    uf.Unite(x, y)

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

Submission status: Accepted

Solution code:
class UnionFind(): 
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n 
        
    def find(self, x): 
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
            
    def union(self, x, y): 
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
    def 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+1)
graph = [[] for _ in range(N)]
can = [[] for _ in range(N)]
xy = list()
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.same(i, P[i-1]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        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 check(self, x, y):
        # 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
        # rankの小さいものを大きいほうにくっつける
        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]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(1, n + 1)})

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(p[x - 1], p[y - 1])

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

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=[int(i)-1 for i in input().split()]
tree=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    tree.union(x-1,y-1)

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

Submission status: Accepted

Solution code:
import collections

N,M = map(int,(input().split()))
p = list(map(int,(input().split())))
line = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,(input().split()))
    line[a-1].append(b-1)

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

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

Tree = UnionFind(N)
for i in range(N):
    for node in line[i]:
        Tree.union(i,node)

d = [[] for _ in range(N)]
e = [[] for _ in range(N)]
for i in range(N):
    d[Tree.root(i)].append(i)
    d[Tree.root(i)].append(p[i]-1)

ans = 0
for i in range(N):
    ans += len(d[i]) - len(set(d[i]))

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_root(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))

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

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

# 順列pに含まれる要素piの値とindex値(+1)が一致、もしくは
# index[i] とindex[p[i]] が同じグループに所属しているときにcount+=1
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):
        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+1)
for i in range(M):
    x,y = map(int,input().split())
    uf.union(x,y)
cnt = 0
for i in range(1,N+1):
    if uf.same(i,p[i-1]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n)]
        # rank
        self.rank = [0] * n
        self.size = [1] * 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 check(self, x, y):
        # 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
        # rankの小さいものを大きいほうにくっつける
        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]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(n)})

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)

#Xj = iなるjを考えたときにi,jが同じ集合に属している時pi = iにできる
cnt = 0
for i in range(n):
    if uf.check(i, p[i] - 1):cnt += 1
print(cnt)