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:
# https://atcoder.jp/contests/arc097/tasks/arc097_b
# Pについてp_xとp_yでuniteしていくと、スワップできる集合が獲得できる
# 1,2,3...i...Nにできるかだが, iについてp_iとiがスワップできるかはunion-findで探せばよい


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


N, M = read_ints()
P = [p - 1 for p in read_ints()]
uf = UnionFind(N)
for _ in range(M):
    x, y = read_ints()
    uf.unite(P[x - 1], P[y - 1])

ans = 0
for i in range(N):
    ans += uf.is_in_same(i, P[i])

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
pi=[0 for i in range(n+1)]
for i,j in enumerate(p,1):
    pi[j]=i
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [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 
        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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.unite(x,y)
ans=0
for i in range(1,n+1):
    if uf.same(i,pi[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

N,M=map(int,input().split())
p=list(map(int,input().split()))
x=[0 for i in range(0,M)]
y=[0 for i in range(0,M)]
for i in range(0,M):
    x[i],y[i]=map(int,input().split())

uf=UnionFindVerSize(N)
for i in range(0,M):
    uf.unite(x[i]-1,y[i]-1)

root=set([])
for i in range(0,N):
    root.add(uf.find_root(i))
root=list(root)
index=[-1 for i in range(0,N)]
for i in range(0,len(root)):
    index[root[i]]=i

tree1=[[] for i in range(len(root))]
tree2=[[] for i in range(len(root))]
for i in range(0,N):
    tree1[index[uf.find_root(i)]].append(i)
    tree2[index[uf.find_root(i)]].append(p[i]-1)

ans=0
for i in range(len(root)):
    set1=set(tree1[i])
    set2=set(tree2[i])
    ans+=len(set1 & set2)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
pi=[0 for i in range(n+1)]
for i,j in enumerate(p,1):
    pi[j]=i
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [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 
        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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.unite(x,y)
ans=0
for i in range(1,n+1):
    if uf.same(i,pi[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 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()))
P = [p - 1 for p in P]
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    uf.union(x, y)
ans = 0
for i, p in enumerate(P):
    if uf.same(p, i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#たどれる2要素の互換が可能
n,m = map(int, input().split( ))

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

E = [tuple(map(int, input().split( ))) for _ in range(m)]

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

###UnionFind
def root(x):
    if x==r[x]:
        return x
    r[x]=y=root(r[x])##
    return y
def union(x,y):
    rx,ry = root(x),root(y)
    if rx!=ry:
        if rank[x]<rank[y]:
            r[rx] = ry##ここrx,ryであってx,yではない
        else:
            r[ry] = rx

for xi,yi in E:
    union(xi,yi)

cnt = 0
for i in range(1,n+1):
    #if r[i]==r[p[i-1]]:
    if root(i)==root(p[i-1]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[-1]*node_size
 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == -1:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える

            # node1のグループをnode0のグループに結合
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
                self.size[root_node0] += self.size[root_node1]

            # node1のグループをnode0のグループに結合
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
                self.size[root_node0] += self.size[root_node1]

            # node0のグループをnode1のグループに結合
            else:
                self.parent[root_node0] = root_node1
                self.size[root_node1] += self.size[root_node0]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)


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

uft = UnionFindTree(N)

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


member_dict = dict()
for i in range(N):
    root = uft.find_root(i)
    p = p_list[i] -1
    if root in member_dict:
        member_dict[root][0].add(i)
        member_dict[root][1].add(p)
    else:
        member_dict[root] = [set([i]),set([p])]

ans = 0
for k in member_dict.keys():
    pos = member_dict[k][0]
    num = member_dict[k][1]
    ans += len(pos&num)
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+1)
    
    for _ in range(M):
        x, y = map(lambda elem: int(elem)-1, input().split())
        uf.unite(p[x], p[y])
    
    cnt = 0
    for i in range(1, N+1):
        if i == p[i-1]:
            cnt += 1
            continue

        if uf.isSame(i, p[i-1]):
            cnt += 1
    
    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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


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を見てくっつける方を決める
      #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)]

uni=UnionFind(N)

for i in range(M):
  x, y=map(int, input().split())
  XY[x-1]=y-1
  XY[y-1]=x-1
  uni.Unite(x-1, y-1)
  
cnt=0
for i in range(N):
  if not uni.isSameGroup(i,P[i]-1):
    cnt+=1
    
print(N-cnt)

Submission status: Accepted

Solution code:
# さっきWAして答えみて再度アタック
# （ちなみに問題自体憶えてないけど昔やったことあってそんときゃACしてたので退化してるね 向いてないね やめたほうがいいね）
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
par = [i for i in range(n)]


def root(x):
    # while x != par[x]:
    #     par[x] = root(par[x])
    # return par[x]
    # なぜか上記の書き方が駄目だった
    if x == par[x]:
        return x
    y = root(par[x])
    par[x] = y
    return y


def union(a, b):
    if a > b:
        a, b = b, a
    ra, rb = root(a), root(b)
    if ra != rb:
        par[ra] = rb


for _ in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    union(x, y)

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self._root = [-1 for _ in range(N)]

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

    def unite(self, x, y):
        gx = self.find(x)
        gy = self.find(y)
        if gx == gy: return False
        if self._root[gx] > self._root[gy]:
            gx, gy = gy, gx
        self._root[gx] += self._root[gy]
        self._root[gy] = gx
        return True

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

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

    def roots(self):
        return [i for i in self._root]


n, m = map(int, input().split())
P = list(map(int, input().split()))
par = []
for _ in range(m):
    x, y = map(int, input().split())
    par.append((x - 1, y - 1))

uf = UnionFind(n)
for i in range(m):
    uf.unite(par[i][0], par[i][1])

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

Submission status: Accepted

Solution code:
class UnionFind:
    parent = []
    rank = []

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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 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
                return self.rank[x]

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

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uf = UnionFind(N)
    
    for _ in range(M):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    
    ans = 0
    for i in range(N):
        if uf.isSame(i, A[i] -1):
            ans += 1

    return ans

print(solve())

Submission status: Accepted

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

par = [-1 for _ in range(n)]

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

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

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

def size(x):
    return par[find(x)]

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

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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

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.same(i,p[i]-1) == True:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
def int_(num):
    return int(num)-1
plist = list(map(int_, input().split()))
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)
ans = 0
for i in range(N):
    if uf.same(i, plist[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
maxn = 100000

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

par = [0] * (n+1)
rank = [0] * (n+1)

#初期化
for i in range(n+1):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1

for _ in range(q):
    a,b = map(int, input().split())
    unite(a,b)

ans = 0
for i in range(n):
    if find(p[i]) == find(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.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)

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

for i, e in enumerate(P):
    if uf.same(i, e-1):
        res += 1

print(res)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
# 同一の集合の判定
def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False
# 集合の辺豪
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

# 集合の数
def uCnt(x):
    return -par[find(x)]

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

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        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 Union(self, x, y):
        #入力ノードの親を探索
        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が同じ(深さが同じ)場合
            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)]
    
    """木(非連結成分)の数を数える"""
    #全連結成分にするために必要な橋の本数は、cnt - 1
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]


n,m = map(int,input().split())
uf = UnionFind(n)
p = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    uf.Union(x,y)
res = 0
for i, x in enumerate(p):
    if uf.isSameGroup(i+1, x):
        res += 1
print(res)

Submission status: Accepted

Solution code:
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


# x,yの属する集合の併合
def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


# xとyが同じグループかどうか判定
def same(x, y):
    return find_root(x) == find_root(y)


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

parent = [i for i in range(N)]  # 根
rank = [1] * N  # 深さ
size = [1] * N  # iを根とするグループのサイズ

edge = [[xy[M - 1 - i][0] - 1, xy[M - 1 - i][1] - 1] for i in range(M)]
for i in range(M):
    unite(edge[i][0], edge[i][1])

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

Submission status: Accepted

Solution code:
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


# x,yの属する集合の併合
def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


# xとyが同じグループかどうか判定
def same(x, y):
    return find_root(x) == find_root(y)


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

parent = [i for i in range(N)]  # 根
rank = [1] * N  # 深さ
size = [1] * N  # iを根とするグループのサイズ

edge = [[xy[M - 1 - i][0] - 1, xy[M - 1 - i][1] - 1] for i in range(M)]
for i in range(M):
    a = find_root(edge[i][0])
    b = find_root(edge[i][1])
    unite(a, b)

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split()) 
P=list(map(int,input().split()))
par=[i for i in range(N+1)]
rank=[0]*(N+1)
#根
def find(x):
  if x==par[x]:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
  
def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
  
#同じ集合か判定
def same(x,y):
  return find(x)==find(y)

def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 0
  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):
  a,b=map(int,input().split())
  union(a,b)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

        if x == y:
            return

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
def main():
    N, M = map(int, input().split())
    P = tuple(map(int, input().split()))
    un = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        un.union(x, y)
    ans = 0
    for i, p in enumerate(P):
        if un.same(i + 1, p):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  #k  = [i,j].min
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]


n,m = inm()
p = inl()
p[0:0] = [0]
x = []
y = []
for i in range(m):
    xx,yy = inm()
    x.append(xx)
    y.append(yy)
ufinit(n+1)
for i in range(m):
    ufconn(x[i],y[i])
ga = [0]*(n+1)
gb = [0]*(n+1)
for i in range(1,n+1):
    r = ufroot(i)
    ga[i] = gb[p[i]] = r
sm = 0
for i in range(1,n+1):
    if ga[i]==gb[i]:
        sm += 1
print(sm)

Submission status: Accepted

Solution code:
class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


N, M = map(int, input().split())
P = list(map(int, input().split()))
uf = UF_tree(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)

ans = 0
for i, p in enumerate(P, start=1):
    if uf.isSame(i, p):
        ans += 1

print(ans)