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:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if (self.parent[i] == i):
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

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


###############################################################################


def main():
    n, m = intin()
    plist = intina()
    xylist = intinl(m)

    u = UnionFind(n)

    for x, y in xylist:
        u.unite(x - 1, y - 1)

    ans = 0

    for i, p in enumerate(plist):
        if u.same(i, p - 1):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind():
    def __init__(self, N):
        self.nodes = [i for i in range(N)]

    def root(self, x):
        if self.nodes[x] != x:
            self.nodes[x] = self.root(self.nodes[x])
        return self.nodes[x]

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

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

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

ans = 0
for idx, p in enumerate(P):
    if tree.is_same(idx, p-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ [int(it)-1 for it in input().split()] for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
    if (len(dw[_a]) < len(dw[_b])):
      _a,_b=_b,_a
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, n):
        self._parents = list(range(n))
        self._ranks = [0] * n

    def root(self, x):
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

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

        if self._ranks[rx] < self._ranks[ry]:
            self._parents[rx] = ry
        else:
            self._parents[ry] = rx
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[rx] += 1


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)

    for xx, yy in zip(x, y):
        uf.unite(xx-1, yy-1)

    ret = 0
    for pp in p:
        if uf.root(pp-1) == uf.root(p[pp-1]-1):
            ret += 1
    print(ret)

# 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:
# https://atcoder.jp/contests/abc097/tasks/arc097_b

import itertools
from collections import Counter
from collections import defaultdict
import bisect

# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]  # 負の値の場合根を表す。絶対値はツリーの高さ 正の値は次の要素を返す、根まで続く
        self.size = [1 for _  in range(size)]

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

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

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

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


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

    uf = UnionFind(N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        uf.union(a, b)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import defaultdict


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):

    par = list(range(N+1))

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

    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):          # O(M)
        unite(x[i], y[i])

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

    return


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:
from sys import exit
class UnionFind():
    #負の値は根で集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        if self.table[x] < 0:return x
        root = self.find(self.table[x])
        self.table[x] = root
        return root

    #併合
    def union(self,x,y):
        s1 = self.find(x)#代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:#代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:#要素数の多い方へMergeする
                self.table[s2] += self.table[s1]#子の和を増やす(-)
                self.table[s1] = s2#Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
        return
    def size(self,x):
        return -self.table[self.find(x)]

N,M = [int(n) for n in input().split()]
p = [int(n) for n in input().split()]

UF = UnionFind(N)
for _ in range(M):
    x,y = [int(n)-1 for n in input().split()]
    UF.union(x,y)
ans = 0
for i in range(N):
    if UF.find(i) == UF.find(p[i]-1):
        ans+=1
print(ans)

Submission status: Accepted

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

class Unionfind:
    def __init__(self, num):
        self.par = [i for i in range(num+1)]
        self.rank = [0] * (num+1)

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[rv] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

    def same(self, u, v):
        return self.root(u) == self.root(v)

uni = Unionfind(N)
for i in range(M):
    x, y = map(int, input().split())
    uni.unite(x, y)

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

print(count)

Submission status: Accepted

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

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

    # 併合
    def 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)


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

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

ans=0
for i in range(N):
    ans+=g.same_check(i+1,p[i])

print(ans)

Submission status: Accepted

Solution code:
N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    if len(glist[gx])<len(glist[gy]):
        gx,gy = gy,gx
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = sum([len(set(row) & set(p[g] for g in row)) for row in glist])
print(out)

Submission status: Accepted

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

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

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#戒めコード
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

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

#root(i)=root(j)ならばiとjは行き来できる(iはjの居る場所に到達できる)
#知りたいのはiがp[i]のいる位置に来れるかどうか
#root(i)=root(p[i])なら,iはp[i]の位置に来れる,すなわちi番目にiを持ってくることができる

Submission status: Accepted

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

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

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

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

Submission status: Accepted

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

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

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

tree = UnionFind(N)

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

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

print(count)

Submission status: Accepted

Solution code:
import collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class UnionFind(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def are_same(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def elements(self, node):
        return self.groups[self.root(node)]

    def size(self, node):
        return len(self.elements(node))

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def grouper(self):
        roots = [x for x in self.par.keys()]
        groups = []
        for root in roots:
            if list(self.elements(root)) not in groups:
                groups.append(list(self.elements(root)))
        return groups


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

graph = UnionFind(range(N))
for x, y in XY:
    graph.unite(P[x-1], P[y-1])

ans = 0
for i in range(N):
    if P[i] == i+1:
        ans += 1
    elif graph.are_same(i+1, P[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


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

uf = uf_tree(n+5)

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

ans = 0

for item_id, item in enumerate(p):
    if uf.same(item, item_id+1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


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


uf = uf_tree(n+5)

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

ans = 0

for item_id, item in enumerate(p):
    if item == item_id + 1:
        ans += 1
    elif uf.same(item, item_id+1):
        ans += 1

print(ans)

Submission status: Accepted

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

par = [0]
rank = [0]
def init(n):
    for i in range(n):
        par.append(i+1)
        rank.append(0)

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

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

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

init(n)
for i in range(m):
    unite(x[i][0],x[i][1])

ans = 0
for i in range(n):
    if same(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()))
p = list(enumerate(p,start=1))
#print(p)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

uf = UnionFind(n)
for m in range(m):
    x,y = map(int,input().split())
    uf.union(x,y)

ans = 0
for now,value in p:
    if uf.same_check(now,value):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.rank = [0] * (n+1)
    self.size = [1] * (n+1)
    
  def union(self, a, b):
    para = self.find(a)
    parb = self.find(b)
    if self.rank[para] > self.rank[parb]:
      self.par[para] = parb
    else:
      self.par[parb] = para
      if self.rank[para] == self.rank[parb]:
        self.rank[para] += 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 is_same(self, a, b):
    return self.find(a) == self.find(b)

n, m = [int(item) for item in input().split()]
p = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(m)]
UF = UnionFind(n)

for x, y in xy:
  UF.union(x,y)
  
ans = 0
for i,item in enumerate(p):
  if UF.is_same(item, i+1):
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[] for i in range(0, n + 1)]
p_set = [[] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

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

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)

for i in range(1, n + 1):
    r = root(i)
    id_set[r].append(i)
    p_set[r].append(p[i])
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        id_i = sorted(id_set[i])
        p_i = sorted(p_set[i])
        k = 0
        for j in range(0, len(id_i)):
            while k < len(p_i) and p_i[k] < id_i[j]:
                k += 1
            if k >= len(p_i):
                break
            if p_i[k] == id_i[j]:
                s += 1

print(s)

Submission status: Accepted

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


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

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

    def 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 pair in pair_lst:
    uf.union(pair[0], pair[1])
    
count = 0
for i in lst:
    if uf.same_check(i, lst[i-1]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
class Union_Find:
    def __init__(self, N):
        self.N = N
        self.par = [i for i in range(N)]
        self.height = [0 for i in range(N)]
        self.size = [1 for i in range(N)]
    def Find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.Find(self.par[x])
        return self.par[x]
    def Size(self, x):
        return self.size[self.Find(x)]
    def Union(self, x, y):
        x, y = self.Find(x), self.Find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1
    def Same(self, x, y):
        return self.Find(x) == self.Find(y)


N, M = map(int, input().split())
p = list(map(int, input().split()))
uf = Union_Find(N + 1)
for _ in range(M):
    x, y = map(int, input().split())
    uf.Union(x, y)
ans = 0
for i in range(N):
    if uf.Same(p[i], i + 1):
        ans += 1
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]
        
    def same(self, x, y):
        return self.root(x)==self.root(y)
 
    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    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
        
uf = UnionFind(N)

for i in range(M):
    x, y = map(int, input().split())
    uf.unite(x - 1, y - 1)
    
cnt = 0
for i in range(N):
    if uf.same(i, P[i] - 1):
        cnt += 1
        #print(i, P[i])
        
print(cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = stdin.readline().rstrip()
    K = II() - 1
    ans = []
    for i in range(len(s)):
        for k in range(K+1):
            b = s[i:i + k + 1]
            ans.append(b)
    ans = list(set(ans))
    ans.sort()
    print(ans[K])
    return

#D
def D():
    n, m = LI()
    p = LI_()
    xy = LIR_(m)
    size = [1 for _ in range(n)]
    height = [1 for _ in range(n)]
    par = [i for i in range(n)]
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if height[s1] < height[s2]:
                par[s1] = s2
                size[s2] += size[s1]
                size[s1] = 0
            else:
                par[s2] = s1
                size[s1] += size[s2]
                size[s2] = 0
                if height[s1] == height[s2]:
                    height[s1] += 1

    for x,y in xy:
        union(x, y)
    ans = 0
    for i in range(n):
        if find(p[i]) == find(i):
            ans += 1
    
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()