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:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    p = list(map(int,input().split()))
    
    I = [i for i in range(N)]
    def root(x):
        if x == I[x]:
            return x
        I[x] = root(I[x])
        return I[x]

    for _ in range(M):
        x,y = map(int,input().split())
        a = root(x-1)
        b = root(y-1)
        if a != b:
            I[b] = a

    c = 0
    for i in range(N):
        if root(p[i]-1) == root(i):
            c += 1
            
    print(c)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0 for _ in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            elif self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[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, y = x-1, y-1
    uf.union(x, y)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n,m = map(int,readline().split())
p = list(map(int,readline().split()))

#Union Find

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

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

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

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""

for i in range(m):
    x,y = map(int,readline().split())
    unite(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:
n,m = map(int, input().split())
p = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(m)]


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    def all_group_members(self):
        return {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):
    uf.union(a[i][0]-1, a[i][1]-1)


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    xy = sorted([tuple(map(int,input().split())) for _ in range(m)])
    d = defaultdict(list)
    for i in xy:
        d[i[0]].append(i[1])
        d[i[1]].append(i[0])
    searched = [False]*n
    c = 0
    graph = []
    allset = set(range(1,n+1))
    while allset:
        xxx = allset.pop()
        pool = set([xxx])
        searched[xxx-1] = True
        g = [xxx]
        gap = g.append
        pad = pool.add
        while pool:
            s = pool.pop()
            tmp = set(d[s])
            dif = tmp&allset
            dad = dif.add
            for i in dif:
                if searched[i-1] is False:
                    dad(i)
                    searched[i-1] = True
                    c += 1
                    gap(i)
                    allset.discard(i)
                    pad(i)
        graph.append(tuple(g))
    ans = 0
    for i in graph:
        ppp = set([p[j-1] for j in i])
        ans += len(ppp&set(i))
    print(ans)
    
if __name__ == '__main__':
    main()

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)

    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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

print(sum(UF.same(i,p) for i,p in enumerate(P)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
T = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x-=1
    y-=1
    T[x].append(y)
    T[y].append(x)

s1 = set()
def dfs(x):
    s1.add(x)
    s2 = set([x])
    stack = [x]
    while stack:
        u = stack.pop()
        for v in T[u]:
            if v not in s1 and v not in s2:
                s1.add(v)
                s2.add(v)
                stack.append(v)
    return s2

ans = 0
for i in range(N):
    if i in s1:
        continue
    I = dfs(i)
    PI = set(P[i] for i in I)
    ans += len(I.intersection(PI))
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()))
pair_list = []
count = 0
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)

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:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

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

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

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


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

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

N,M=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)

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

Submission status: Accepted

Solution code:

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            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 weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)



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

"""    
Unionfindで、自由に移動できるindexを同定
その中で、indexと数字がおなじになるものを同定
"""
uf = UnionFind(n)
for i in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    if not uf.judge(x,y):
        uf.union(x,y)

ps = [p-1 for p in ps]

ans = 0
for i,p in enumerate(ps):
    if uf.judge(i,p):
        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())
pl = list(map(int,input().split()))
uf = UnionFind(n)
for _ in range(m):
   x,y = map(int,input().split())
   uf.union(x-1,y-1)
ans = 0
for idx,p in enumerate(pl):
   ans += uf.same(p-1,idx)
print(ans)

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
*p, = map(int, sys.stdin.readline().split())
xy = list(zip(*[map(int, sys.stdin.read().split())] * 2))

g = [[] for _ in range(n+1)]
for x, y in xy:
    g[x-1].append(y-1)
    g[y-1].append(x-1)

root = list(range(n))
height = [0] * n

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def unite(v, u):
    rv = find_root(v)
    ru = find_root(u)
    if root[rv] == root[ru]:
        return
    if height[rv] >= height[ru]:
        root[ru] = rv
        height[rv] = max(height[rv], ru+1)
    else:
        root[rv] = ru

def main():
    for x, y in xy:
        unite(x-1, y-1)

    for i in range(n):
        find_root(i)
    
    cnt = 0
    for i in range(n):
        cnt += (root[i] == root[p[i]-1]) & 1
    
    return cnt
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

import sys

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

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

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

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

    def union(self, x, y):
        """ 併合 """
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

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

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            # グループ0の分を引いて返却
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
A = LIST()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    uf.union(a, b)

ans = 0
for i, a in enumerate(A):
    # UnionFindが繋がっているなら、スワップを繰り返してその場所に移動できる
    if uf.is_same(i+1, a):
        ans += 1
print(ans)

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


if __name__ == "__main__":
    n, m = map(int, input().split())
    p = tuple(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 in range(n):
        if uf.isSame(p[i], i + 1):
            ans += 1
    print(ans)

Submission status: Accepted

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

root = [i for i in range(N + 1)]
comp_size = [1] * (N + 1)

def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if sx >= sy:
    comp_size[rx] += comp_size[ry]
    root[ry] = root[rx]
  else:
    comp_size[ry] += comp_size[rx]
    root[rx] = root[ry]

for _ in range(M):
  a, b = map(int, input().split())
  merge(a, b)
#print(root)

answer = 0
for i in range(N):
  if root_find(P[i]) == root_find(i + 1):
    answer += 1
#print(root)
print(answer)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    P = [int(i)-1 for i in input().split()]
    for i in range(M):
        x, y = (int(i)-1 for i in input().split())
        unite(x, y)
    ans = 0
    for i, p in enumerate(P):
        if is_same_group(i, p):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M=MI()
    P=LI_()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    XY=LLIN_(M)
    for x,y in XY:
        unite(x,y)

    ans = 0
    for i,a in enumerate(P):
        ans += get_root(i)==get_root(a)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


class UnionFind:
    def __init__(self, num):
        self.parent = list(range(num))

    def get_root(self, node):
        root = self.parent[node]
        if root == node:
            return root
        else:
            root = self.get_root(root)
            self.parent[node] = root
            return root

    def are_in_same_union(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return True
        else:
            return False

    def unite(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        if root1 == root2:
            return
        self.parent[root2] = root1


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


count = 0
for i in range(n):
    num = P[i]
    if num == i:
        count += 1
    else:
        if uf.are_in_same_union(i, num):
            count += 1

print(count)

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

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

ans = 0
for i, p in enumerate(P, start=1):
    if tree.isSameRoot(i, p):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#%%
n, m = map(int, input().split())
p = list(map(int, input().split()))
x, y = [0] * m, [0] * m
reach = [[] for _ in range(n + 1)]
for i in range(m):
    x[i], y[i] = map(int, input().split())
    reach[x[i]].append(y[i])
    reach[y[i]].append(x[i])


check = [0] * (n + 1)
color = [-1] * (n + 1)
c = -1

for i in range(n + 1):
    if check[i] == 1:
        pass
    else:
        c += 1
        check[i] = 1
        stack = reach[i]
        color[i] = c
        while len(stack) >= 1:
            tmp = stack.pop(-1)
            color[tmp] = c
            check[tmp] = 1
            tmp_list = reach[tmp]
            for i in range(len(tmp_list)):
                if check[tmp_list[i]] == 0:
                    stack.append(tmp_list[i])
                    check[tmp_list[i]] = 1
                else:
                    pass

color.pop(0)
#print(color)

ans_list = [0] * n
for i in range(n):
    ans_list[i] = color[p[i] - 1]
#print(ans_list)

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