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:
def Root(x, cnt):
  cnt += 1
  if L[x] == x:
    return x, cnt
  else:
    return Root(L[x], cnt)

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

Data = []
for i in range(M):
  Data.append(list(map(int, input().split())))

L = [i for i in range(N + 1)]
for i in Data:
  a = Root(i[0], 0)
  b = Root(i[1], 0)
  if a[1] > b[1]:
    L[b[0]] = L[a[0]]
  else:
    L[a[0]] = L[b[0]]
    
Ans = 0
for i in range(N):
  if Root(i + 1, 0)[0] == Root(p[i], 0)[0]:
    Ans += 1
print(Ans)

Submission status: Accepted

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
n,m = list(map(int,input().split()))
p = list(map(int,input().split()))
uft = UnionFind(n)

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

Submission status: Accepted

Solution code:
#UnionFind
def root(nodes,x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes,nodes[x])
        return nodes[x]

def unite(nodes,x,y):
    root_x, root_y = root(nodes,x) , root(nodes,y)
    if root_x != root_y:
        nodes[root_x] = root_y

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



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

for x,y in x_y:
    unite(nodes,x,y)


for i in range(N):
    if is_same(nodes,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()))
XY = [tuple(map(int,input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)

# 交換可能な頂点でグルーピング
A = UnionFind(N)
for (x,y) in XY:
    A.unite(x,y)

# 頂点の数字(P[i]) と頂点番号(i+1) が同じグループかどうか
ans = 0
for i in range(N):
    if A.check(i+1,P[i]):
        ans += 1

print(ans)

Submission status: Accepted

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

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

# xの根を見つける
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
  
# x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
def find(x, y):
  return root(x) == root(y)

# xとyの根を結合させる
def union(x, y):
  x = root(x)
  y = root(y)
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]:
      rank[x] += 1

for i in range(m):
  union(info[i][0],info[i][1])

a=[0]*(n+1)
for i in range(n):
  a[p[i]]=i+1

ans = 0 
for i in range(1,n+1):
  if find(i,a[i]):
    ans += 1
    
print(ans)

Submission status: Accepted

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

follow = [i for i in range(n)]
num = [1]*n
def root_index_of(x):
    r = x
    while follow[r] != r:
        r = follow[r]
    return r

def connected(x, y):
    return root_index_of(x) == root_index_of(y)

def connect(x, y):
    rx = root_index_of(x)
    ry = root_index_of(y)

    if rx == ry:
        return

    if num[rx] < num[ry]:
        follow[rx] = ry
        follow[x] = ry
        num[ry] += num[rx]
    else:
        follow[ry] = rx
        follow[y] = rx
        num[rx] += num[ry]

for i in range(m):
    x, y = map(lambda x: x-1, map(int, input().split()))
    connect(p[x], p[y])

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

Submission status: Accepted

Solution code:
class UnionFind:
    # 負の値はルートで集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            # 根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:  # 根が異なる場合
            if self.table[s1] != self.table[s2]:  # グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                # グラフの長さが同じ場合,どちらを根にしても変わらない
                # その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return


def func(n, m, p, x):
    union = UnionFind(n + 1)
    for _x in x:
        union.union(p[_x[0]], p[_x[1]])
    count = 0
    for i in range(n):
        if union.find(i + 1) == union.find(p[i]):
            count += 1
            # print("{}:{}".format(i, union.find(i)))
            # 所属しているunionの根の値を出力する
    # print([union.find(i) for i in range(n+1)])
    return str(count)


n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[0, 0] for _ in range(m)]
for i in range(m):
    x[i] = [int(i) - 1 for i in input().split()]
print(func(n, m, p, x))
"""
print(str(2) + " vs " + func(5, 2, [5, 3, 1, 4, 2], [[0, 2], [4, 3]]))
print(str(3) + " vs " + func(3, 2, [3, 2, 1], [[0, 1], [1, 2]]))
print(str(8) + " vs " + func(10, 8, [5, 3, 6, 8, 7, 10, 9, 1, 2, 4],
                             [[2, 0], [3, 0], [4, 8], [1, 4], [5, 4], [2, 4], [7, 8], [6, 8]]))
print(str(5) + " vs " + func(5, 1, [1, 2, 3, 4, 5], [[0, 4]]))
# print("print(func({}, {}, {}, {}))".format(n, m, p, x))
"""

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    N, M = na[0], na[1]
    p = list(map(int, input().split()))
    x_list = [None] * (N + 1)
    y_list = [None] * (N + 1)
    for i in range(M):
        na = list(map(int, input().split()))
        x, y = na[0], na[1]
        if x_list[x] is None:
            x_list[x] = [y]
        else:
            x_list[x].append(y)
        if y_list[y] is None:
            y_list[y] = [x]
        else:
            y_list[y].append(x)

    visited = [False] * (N + 1)
    connections = [None] * (N + 1)
    for i in range(1, N + 1):
        if not visited[i]:
            q = []
            c = set()
            visited[i] = True
            q.append(i)
            while 0 < len(q):
                j = q.pop(0)
                c.add(j)
                if not x_list[j] is None:
                    for k in x_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
                if not y_list[j] is None:
                    for k in y_list[j]:
                        if not visited[k]:
                            visited[k] = True
                            q.append(k)
            if 1 < len(c):
                connections[i] = c

    cn = 0
    counted = [False] * (N + 1)
    for i in range(1, N + 1):
        if not connections[i] is None:
            c = connections[i]
            for j in c:
                if p[j - 1] in c:
                    cn += 1
                counted[j] = True
    for i in range(1, N + 1):
        if not counted[i]:
            if p[i - 1] == i:
                cn += 1

    print(cn)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N+1)]
        self.rank=[0 for _ in range(N+1)]
    
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def same_check(self,x,y):
        return self.find(x)==self.find(y)
    
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

n,m=map(int,input().split())
s=list(map(int,input().split()))
l=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    l.union(x,y)
cnt=0
for i in range(n):
    if l.same_check(s[i],i+1):
        cnt+=1
print(cnt)

Submission status: Accepted

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


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

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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

ans = 0
for i, p in enumerate(P):
    ans += UF.same(i, p - 1)

print(ans)

Submission status: Accepted

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

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
p_list = list(map(int, input().split()))
union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    union_find.union(x, y)

result = 0
for i in range(N):
    if union_find.check_same(p_list[i], i + 1):
        result += 1
print(result)

Submission status: Accepted

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

"""
参考：http://at274.hatenablog.com/entry/2018/02/02/173000
・Union-Find木
"""

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

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


N, M = map(int, input().split())
pN = list(map(int, input().split()))
uf = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    uf.union(x, y)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = input().split()
a = [int(m) for m in a]
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return

class UnionFind2(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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

#print(s[1][0], s[1][1])
u = UnionFind(n)
for i in range(m):
    u.union(s[i][0] - 1, s[i][1] - 1)
    k = u.table
k = u.table
#rt = u.find()
#print(u.parent)
#a = [5,3,1,4,2]
count = 0
for i in range(n):
    if u.find(i) == u.find(a[i] - 1):
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque, defaultdict
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
visited = [False for _ in range(N)]

for x,y in xy:
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = True
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   #深さ優先探索
        # i = que.popleft() #幅優先探索
        for n in list(graph[i]):
            if visited[n] == False:
                visited[n] = True
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == False:
        grps.append(dfs(i))

ans = 0
for g_list in grps:
    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)

Submission status: Accepted

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

class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)

Submission status: Accepted

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

class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
  
  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root
    
  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
    
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[i for i in range(N)]
def find(x):
  if x==Tree[x]:
    return x
  else:
    root=find(Tree[x])
    Tree[x]=root
    return root
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    Tree[s1]=s2
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def Union(x,y,par):
    x = Find(x,par)
    y = Find(y,par)
    if par[x] < par[y]:
        par[y] = par[x]
    else:
        par[x] = par[y]

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

n,m=map(int,input().split())
p =list(map(int,input().split()))
par=[i for i in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    Union(x,y,par)
ans = 0
for i in range(n):
    ans += 1 if Find(p[i]-1,par)==Find(i,par) else 0
print(ans)

Submission status: Accepted

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

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

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


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

uf = UnionFind(n)

for x, y in info:
    uf.merge(p[x-1]-1, p[y-1]-1)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

n,m = li()
p = list(li_())
xy = []
for _ in range(m):
    xy.append(tuple(li_()))
    
uf = UnionFind(n)

for x,y in xy:
    uf.unite(x,y)
    
rtnode = {i:set() for i in range(n)}
number = {i:set() for i in range(n)}

for i in range(n):
    uf.find(i)
    rtnode[uf.par[i]].add(i)
    number[uf.par[i]].add(p[i])
    
ans = 0
for i in range(n):
    ans += len(rtnode[i] & number[i])
    
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y in src:
    x,y = x-1,y-1
    if uf.is_same(x,y): continue
    uf.unite(x,y)

bags = [set() for i in range(N)]
for i in range(N):
    r = uf.root(i)
    bags[r].add(i)

ans = 0
for i in range(N):
    for j in bags[i]:
        if P[j]-1 in bags[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
class Union_find:
    def __init__(self,n):
        self.group=[i for i in range(n)]
    
    def root(self,x):
        if(self.group[x]==x):
            return x
        else:
            tmp=self.root(self.group[x])
            self.group[x]=tmp
            return tmp
    
    def make(self,x,y):
        self.group[self.root(x)]=self.root(y)
    
    def judge(self,x,y):
        if(self.root(x)==self.root(y)):
            return True
        else:
            return False


n,m=map(int,input().split())
T=Union_find(n+1)
P=list(map(int,input().split()))

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


ans=0

for i in range(n):
    if(T.judge(P[i],i+1)):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self._par = [i for i in range(n)]
        self._rnk = [0 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return

        if self._rnk[x] < self._rnk[y]:
            x, y = y, x

        if self._rnk[x] == self._rnk[y]:
            self._rnk[x] += 1

        self._par[y] = x

    def is_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):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)

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

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

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

ans = 0
for i, n in enumerate(p, 1):
    ans += g.find(i) == g.find(n)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def run(self, N, M, p, x):
        '''Union find(ランクなし)'''
        # 初期化。index0はとりあえず0で埋める
        self.part = []
        for i in range(N+1):
            self.part.append(i) 
        # 経路をまとめる
        for i in range(M):
            self.union(x[i][0], x[i][1])
        cnt = 0
        for i in range(1, N+1):
            if self.root(i) == self.root(p[i-1]):
                cnt += 1
        return cnt

    def root(self, x):
        if self.part[x] == x:
            return x
        else:
            # 経路圧縮
            self.part[x] = self.root(self.part[x])
            return self.part[x]
    
    def union(self, x, y):
        x_root = self.root(self.part[x])
        y_root = self.root(self.part[y])
        if x_root == y_root:
            pass
        else:
            self.part[x_root] = y_root


def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    x = []
    for i in range(M):
        x.append(list(map(int, input().split())))
    obj = UnionFind()
    print(obj.run(N, M, p, x))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
par = list(range(n+1))

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

for _ in range(m):
    x, y = map(int, input().split())
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    if i in paths.keys():
        stack = deque(paths[i])
        cluster = set([i]+paths[i])
    else:
        stack = []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in cluster:
                stack.append(k)
                cluster.add(k)
    path_id += 1
# print(connected)

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

Submission status: Accepted

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


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

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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


UF.all_find()

ans = 0
for index, number in P:
    ans += UF.same(index, number - 1)

print(ans)