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:
#Union Findで連結を判定
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(M)]

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    x-=1
    y-=1
    U.merge(x,y)
print(sum(U.is_united(i,p-1) for i,p in enumerate(P)))

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+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 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
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
ans=0
for i in range(n):
    if uf.same_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()))
XY = [list(map(int, input().split())) for _ in range(M)]


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

uni = UnionFind(N)
for x, y in XY:
    uni.Unite(x, y)

group = {}
for i, r in enumerate(uni.root):
    if r < 0:
        group[i] = set([i])
for i, r in enumerate(uni.root):
    if r > 0:
        w = uni.Find_Root(i)
        group[w].add(i)

ans = 0
for k, v in group.items():
    if k == 0:
        continue
    L = set()
    for ind in v:
        L.add(P[ind-1])
    ans += len(v & L)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

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

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

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

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


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.unite(x[i]-1, y[i]-1)
    counter = 0
    for i in range(N):
        if uf.is_same_group(i, p[i]-1):
            counter += 1
    print(counter)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]" 
    y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

XY = [0]*M
for i in range(M):
    X, Y = [int(x) for x in input().split()]
    XY[i] = X, Y

# x != y

parent = [x for x in range(N+1)]

def union(x, y):
    px = find(x)
    py = find(y)
    if px != py:
        parent[py] = px
    # if px != py:
    #    parent[x] = px
    #    parent[y] = px

def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]
        
for x, y in XY:
    union(x, y)

cnt = 0
if False:
    print("P     ", " ".join(str(x) for x in P))
    print("parent", " ".join(str(x) for x in parent[1:]))
    print("same  ", " ".join("*" if find(i+1) == find(p) else " " for i, p in enumerate(P)))
for i, p in enumerate(P):
    if find(i+1) == find(p):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def find(x):
    while union[x] != x:
        x = union[x]
        
    return x

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

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

for i in range(M):
    x, y = map(int, input().split())
    x = find(x)
    while union[y] != y:
        union[y], y = x, union[y]
        
    union[y] = x
    
ans = 0
for idx, n in enumerate(p):
    if idx+1 == n:
        ans += 1
    else:
        x, y = find(idx+1), find(n)
        if x == y:
            ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            
N, M = map(int, input().split())

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

uni = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if uni.same(x, y):
        pass
    else:
        uni.connect(x, y)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

UF=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    UF.Unite(x,y)
ans=0
for i in range(n):
    if UF.isSameGroup(i+1,p[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

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

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


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

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

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

Submission status: Accepted

Solution code:

"""
方針
ペアになっているものは、順序が任意になるという認識
-> UnionFindで行ける
"""

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0 for i 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y
    
    # 判定
    def judge(self,x,y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
ps = list(map(int, input().split()))
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)
ans = 0
for i,p in enumerate(ps):
    if uf.find(p-1) == uf.find(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)
        
    def Find_root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        x = self.Find_root(x)
        y = self.Find_root(y)
        if (x == y):
            return
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_root(x) == self.Find_root(y)
    
    def Count(self, x):
        return - self.root[self.Find_root(x)]
    
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
union = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    union.Unite(x - 1, y - 1)
count = 0
for i, pp in enumerate(p):
    if union.Find_root(i) == union.Find_root(pp - 1):
        count += 1
print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n,m=map(int,input().split())
p=list(map(int,input().split()))
l=[list(map(int,input().split())) for _ in range(m)]
UF=UnionFind(n)
for i in l:
    UF.Unite(i[0],i[1])
ans=0
for i in range(n):
    if UF.isSameGroup(i+1,p[i]):ans+=1
print(ans)

Submission status: Accepted

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

    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 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 are_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, y)

ans = 0
for n in range(N):
    if uf.are_same(P[n], n+1):
        ans += 1

print(ans)

Submission status: Accepted

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

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

node_list = [UnionFindNode(i) for i in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    node_list[x-1].unite(node_list[y-1])

ans = 0
for i, p in enumerate(p_array):
    if node_list[i].find() == node_list[p-1].find() or i == p-1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.size = n
        self.data = [-1 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


N, M = map(int, input().split())
p = [int(s) - 1 for s in input().split()]
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)
ans = [uf.connected(i, v) for i, v in enumerate(p)].count(True)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split());p=list(map(int,input().split()));z=0;import sys;sys.setrecursionlimit(10**9);f=[i for i in range(n)]
def r(f,x):
  if f[x]!=x:f[x]=r(f,f[x])
  return f[x]
def u(f,a,b):
  x,y=r(f,a),r(f,b)
  if x!=y:f[x]=y
for i in range(m):a,b=map(int,input().split());u(f,a-1,b-1)
for i in range(n):z+=r(f,i)==r(f,p[i]-1)
print(z)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
ans=0
import sys;sys.setrecursionlimit(10**9)
class u():#UnionFind f-根探し u-連結 s-連結? c-要素数
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
u=u(n)
for i in range(m):
  a,b=map(int,input().split())
  u.u(a-1,b-1)
for i in range(n):
  if p[i]==i+1:ans+=1
  elif u.f(i)==u.f(p[i]-1):ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
arr=list(map(int,input().split()))
t=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  t.Unite(a,b)
ans=0
for i in range(n):
  if arr[i]==(i+1):
    ans+=1
  else:
    if t.isSameGroup((i+1),arr[i]):
      ans+=1
print(ans)

Submission status: Accepted

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

P = [int(x) - 1 for x in input().split()]

pear = []
for i in range(M):
	pear.append([int(x) - 1 for x in input().split()])


par = []
for i in range(N):
	par.append(i)

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

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

def unite(x, y):
	X = root(x)
	Y = root(y)
	if X != Y:
		par[X] = Y

for i in range(M):
	unite(pear[i][0], pear[i][1])

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
#Union Findで連結を判定
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

class UnionFind:
    def __init__(self,N):
        self.Parent = [-1]*N
    def get_Parent(self,n):
        if self.Parent[n] == -1:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
for x,y in XY:
    x-=1
    y-=1
    U.merge(x,y)
print(sum(U.is_united(i,p-1) for i,p in enumerate(P)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

def get_Parent(n):
    if Parent[n] == -1:return n
    par = get_Parent(Parent[n])
    Parent[n] = par
    return par
def merge(x,y):
    x = get_Parent(x)
    y = get_Parent(y)
    if x!=y: Parent[y] = x
    return
def is_united(x,y):
    return get_Parent(x)==get_Parent(y)

Parent = [-1]*N
for x,y in XY:
    x-=1
    y-=1
    merge(x,y)
print(sum(is_united(i,p-1) for i,p in enumerate(P)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for x,y in XY:
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
def connect_bfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

done = [False]*N
ans = 0
for i in range(N):
    if done[i]:continue
    J = connect_bfs(N,E,i)
    PJ = set(P[j]-1 for j in J)
    ans += len(J & PJ)
    for j in J:
        done[j] = True
print(ans)

Submission status: Accepted

Solution code:
def solve(p, query):
    ans = 0
    for a, b in query:
        unite(a, b)

    for pi in p:
        if is_same(pi, p[pi]):
            ans += 1

    return ans


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


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


def unite(x, y):
    rt_x = find(x)
    rt_y = find(y)
    if rt_x == rt_y:
        return
    if rnk[rt_x] < rnk[rt_y]:
        par[rt_x] = rt_y
    else:
        par[rt_y] = rt_x
        if rnk[rt_x] == rnk[rt_y]:
            rnk[rt_x] += 1


if __name__ == '__main__':
    n, m = map(int, input().split())
    query = []
    par, rnk = [0]*n, [0]*n
    p = list(map(int, input().split()))
    p = list(map(lambda x: x-1, p))

    for _ in range(m):
        a, b = map(int, input().split())
        query.append((a-1, b-1))

    for i in range(n):
        par[i] = i

    print(solve(p, query))

Submission status: Accepted

Solution code:
class union_find:

    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

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

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

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

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

        self.par[x] += self.par[y]
        self.par[y] = x
        return

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

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

uf = union_find(n)

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

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

print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = list(map(lambda v: int(v) - 1, input().split()))
grp = []
for i in range(0, N):
	grp.append(i)
for i in range(0, M):
	X, Y = map(lambda v: int(v) - 1, input().split())
	rootX = X
	que1 = []
	while True:
		if grp[rootX] == rootX:
			break
		que1.append(rootX)
		rootX = grp[rootX]
	for j in range(0, len(que1)):
		grp[que1.pop(0)] = rootX
	rootY = Y
	que2 = []
	while True:
		if grp[rootY] == rootY:
			break
		que2.append(rootY)
		rootY = grp[rootY]
	for j in range(0, len(que2)):
		grp[que2.pop(0)] = rootY
	grp[rootX] = rootY
cnt = 0
for i in range(0, N):
	root1 = i
	que1 = []
	while True:
		if grp[root1] == root1:
			break
		que1.append(root1)
		root1 = grp[root1]
	for j in range(0, len(que1)):
		grp[que1.pop(0)] = root1
	root2 = P[i]
	que2 = []
	while True:
		if grp[root2] == root2:
			break
		que2.append(root2)
		root2 = grp[root2]
	for j in range(0, len(que2)):
		grp[que2.pop(0)] = root2
	if root1 == root2:
		cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
P = list(map(lambda x:int(x)-1,input().split()))

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

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


uf = UnionFind(n)

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

Submission status: Accepted

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


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

#連結成分に属するかどうかを見るときはUnion-Findを用いる
#根(属するクラス)を返す関数
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
#同じクラスに属するかどうかを返す関数
def same(x,y):
    return root(x) == root(y)
#木を結合する関数
def union(x,y):
    x = root(x)
    y = root(y)
    #高さの高いほうに低いほうを結合
    if rank[x] < rank[y]:
        par[x] = y#xの親(属するクラス)をyとする
    else:
        par[y] = x
        if rank[x] == rank[y]:#高さが同じ場合
            rank[x] += 1#高さは1つ増える
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    #swapできる頂点は同じ木にして同じ連結成分にする
    if not same(x-1,y-1):
        union(x-1,y-1)

ans = 0
for i in range(n):
    #p[i]とiが同じ連結成分ならばans+1
    if root(p[i]) == root(i):
        ans += 1
print(ans)

Submission status: Accepted

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

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

    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 = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

N,M = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
un = UnionFind(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    un.unite(x-1,y-1)
cnt = 0
for ind,i in enumerate(p):
    if(un.same(ind,i-1)):
        cnt+=1
print(cnt)