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 collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

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


n, m = MI()
p = LI()
pair = [LI() for _ in range(m)]
uf = UnionFind(n)
for x, y in pair:
    uf.unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if uf.same(p[i] - 1, i):
        ans += 1
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 [0]*M]
z=[[i,1] for i in range(N)]

def root_find(a):
    while(a!=z[a][0]):
        a=z[a][0]
    return a

def union(a,b):
    ra=root_find(a[0])
    rb=root_find(b[0])
    if z[ra][1]<=z[rb][1]:
        z[ra][0]=rb
        z[rb][1]=max(z[rb][1],z[ra][1]+1)
    else:
        z[rb][0]=ra
        z[ra][1]=max(z[ra][1],z[rb][1]+1)
    
for i in range(M):
    union(z[xy[i][0]],z[xy[i][1]])

for i in range(N):
    z[i][0]=root_find(z[i][0])

dic=dict()

for i in range(N):
    zz=z[i][0]
    if zz not in dic.keys():
        dic[zz]=[i]
    else:
        dic[zz].append(i)

list1=list(dic.values())
list2=[[p[a] for a in list1[i]] for i in range(len(list1))]

cnt=sum(len(set(list1[i])&set(list2[i])) for i in range(len(list1)))
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

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

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

a = defaultdict(list)
b = defaultdict(list)
for i in range(n):
    k = uf.find(i)
    a[k].append(i)
    b[k].append(p[i])

ans = 0
for k in a.keys():
    ans += len(set(a[k]) & set(b[k]))

print(ans)

Submission status: Accepted

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

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
N,M = map(int,input().split())
u = UnionFind(N)
p = list(map(int,input().split()))
for _ in range(M):
    x,y = map(int,input().split())
    u.union(p[x-1]-1,p[y-1]-1)

ans = 0
for i in range(N):
    if u.find(i) == u.find(p[i]-1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =[int(i) for i in range(size)]
        self.grp =size

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        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 group_num(self):
        return self.grp


n,m=map(int, input().split())
p=[int(i) for i in input().split()]
uf=UnionFind(n+1)

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

ans=chk=0
for a,i in enumerate(p):
    if uf.same(p[a],a+1): ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

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

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

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

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

ct=0
for i in range(n):
  if UF.find_root(i)==UF.find_root(p[i]-1):ct+=1
print(ct)

Submission status: Accepted

Solution code:


def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind =  data[i]
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
plist = list(map(int, input().split()))

parent = [i for i in range(n)]
height = [1 for _ in range(n)]

def root(i):
  if parent[i] != i:
    parent[i] = root(parent[i])
  return parent[i]

def union(i, j):
  pi = root(i)
  pj = root(j)
  if pi == pj:
    return
  else:
    if height[pi] < height[pj]:
      parent[pi] = pj
    elif height[pi] > height[pj]:
      parent[pj] = pi
    else:
      if pi < pj:
        parent[pj] = pi
        height[pi] += 1
      else:
        parent[pi] = pj
        height[pj] += 1

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

ans = 0
for i, p in enumerate(plist):
  if root(i) == root(p-1):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, M = map(int, input().split())
P = list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

group = [0]*(N+1)
ans = 0
for i,num in enumerate(P,1):
    ex_space = [i]
    for ex_point in ex_space:
        if group[ex_point]:
            continue
        group[ex_point] = i
        ex_space.extend(graph[ex_point])
    ans += (group[num] == group[i])
 
print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import copy

sys.setrecursionlimit(10**5)

# 木の根を返す
def find(x, S):
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]

# xとyが同じ集合に属すかの判定
def same(x, y, S):
    return find(x, S) == find(y, S)

# xとyの属する集合を結合
def unite(x, y, S):
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [N, M] = [int(i) for i in input().split()]

    S = [int(i) for i in range(N+1)]
    p = [0] + [int(num) for num in input().split()]

    for i in range(M):
        [x, y] = [int(i) for i in input().split()]
        unite(x, y, S)

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

Submission status: Accepted

Solution code:
N,M = [int(s) for s in input().split()]
p = [0] + [int(s) for s in input().split()]
par = []
counter = 0

for i in range(N+1):
    par.append(i)
    
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

for i in range(M):
    x,y = [int(s) for s in input().split()]
    union(x,y)
    
for i in range(1,N+1):
    if same(i,p[i]):
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in read(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    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)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


def main():
    N, M = readi(2)
    ips = {ip[1]: ip for ip in enumerate(readi(N), 1)}
    uf = UnionFind(ips.values())
    for _ in range(M):
        x, y = readi(2)
        uf.unite(ips[x], ips[y])

    ans = 0
    for g in uf.grouper():
        iss, ps = zip(*g)
        ans += len(iss) - len(set(iss) - set(ps))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#union-find-tree
import sys
sys.setrecursionlimit(10**7)
def init(n):
    return list(range(n+1))
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N, M = map(int, input().split())
union_find_lis = init(N)
P = [0] + [int(s) for s in input().split()]
for _ in range(M):
    x, y = map(int, input().split())
    union(union_find_lis, x, y)
count = 0
for index in range(1, N+1):
    if sameset(union_find_lis, P[index], index):
        count += 1
print(count)

Submission status: Accepted

Solution code:
#union-find-tree
def init(n):
    lis = []
    for i in range(n+1):
        lis.append(i)
    return lis
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N, M = map(int, input().split())
input_lis = [0]+[int(p) for p in input().split()]
union_find_lis = init(N)
for _ in range(M):
    x, y = map(int, input().split())
    union(union_find_lis, x, y)
count = 0
init_flag = True
for index, num in enumerate(input_lis):
    if init_flag:
        init_flag = False
    else:
        if sameset(union_find_lis, index, num):
            count += 1
print(count)

Submission status: Accepted

Solution code:
# 1,3を入れ替えたあとに3,5を入れ替えれば1,5が入れ替わるパターンが難しいポイント
# イメージ：ある頂点を入れる->つながっている辺が返ってくる。その中で該当のものがあれば交換する？
class Tree():
    def __init__(self, array):
        n = len(array)
        # 最初はすべてを根として定義する
        self.roots = [x for x in range(n + 1)]

    def get_root(self, a):
        if self.roots[a] == a:
            return a
        else:
            self.roots[a] = self.get_root(self.roots[a])
            return self.roots[a]

    def unite(self, x, y):
        if self.get_root(x) == self.get_root(y):
            pass
        else:
            self.roots[self.get_root(y)] = self.get_root(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    p_array = [int(x) for x in input().split()]
    xy_array = [[int(x) for x in input().split()] for y in range(m)]

    tree = Tree(p_array)

    # 連結しなおす
    for x, y in xy_array:
        tree.unite(x, y)

    res = 0
    for i in range(1, n + 1):
        if tree.get_root(i) == tree.get_root(p_array[i-1]):
            res += 1
    print(res)

Submission status: Accepted

Solution code:
class UnionFind(object):
    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
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def 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
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            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())
    tree.union(x, y)
ans = 0
for i, pi in enumerate(p):
    if tree.check(i + 1, pi):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# abcde    s=input()    s='abcde'
# abcde    s=list(input())    s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)    a=int(input())    a=5
# 1 2    | x,y = s_inpl()   |    x=1,y=2
# 1 2 3 4 5 ... n 　    li = input().split()    li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　    li = inpl()    li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　    li = input().split('T')    li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

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

class UnionFind(object):
 
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            x, y = y, x
 
        self.size[x] += self.size[y]
        self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count(self, x):
        return self.size[self.find(x)]

N, M = l_inpl()
p = l_inpl()

uf = UnionFind(N)
for _ in range(M):
    xi, yi = l_inpl()
    xi, yi = xi-1, yi-1
    uf.union(xi, yi)

ans = 0
for i, pi in enumerate(p):
    pi = pi - 1
    if uf.same(i, pi):
        ans += 1

print(ans)

Submission status: Accepted

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


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


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uni = UnionFind(N)
    for xx,yy in zip(x,y):
        uni.Unite(xx-1,yy-1)  

    cnt = 0
    for i,pp in enumerate(p):
        if  i+1 == pp or uni.isSameGroup(i,pp-1):
            cnt += True

    print(cnt)

    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(i) for i in input().split()]
l=[0 for i in range(n)]
for i in range(n):
    l[p[i]-1]=i
xy=[]

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

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(m):
    a=[int(j)-1 for j in input().split()]
    xy.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

N,M = map(int,input().split())
p = list(map(int,input().split()))
xy = [list(map(int,input().split())) for i in range(M)]
un = UnionFind(N)
ans = 0
for i in range(M):
    un.union(xy[i][0]-1,xy[i][1]-1)
for i in range(N):
    if un.same_group_or_no(i,p[i]-1):
        ans += 1

print(ans)

Submission status: Accepted

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

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

p = [0] + [int(x) for x in input().split()]
root = list(range(N+1))
depth = [0]*(N+1)

# 連結成分を作る
def find_root(x):
  y = root[x]
  if x == y:
    return y
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  xx = find_root(x)
  yy = find_root(y)
  if xx == yy:
    return
  if depth[xx] > depth[yy]:
    root[yy] = xx
  elif depth[xx] < depth[yy]:
    root[xx] = yy
  else:
    root[xx] = yy
    depth[xx] += 1
    
XY = [[int(x) for x in input().split()] for _ in range(M)]
for x,y in XY:
  merge(x,y)

# 連結成分内は自由に作れる
# p[i]とiが同じ連結成分にあると1点
answer = 0
for i,x in enumerate(p[1:],1):
  if find_root(i) == find_root(x):
    answer += 1

print(answer)

Submission status: Accepted

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

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

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

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

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

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

for i in range(m):
    x, y = map(int, input().split())
    union(p[x - 1], p[y - 1])
ans = 0
for i in range(n):
    if same_check(i + 1, p[i]):
        ans += 1
print(ans)

Submission status: Accepted

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

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

    # 併合
    def 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=list(map(int,input().split()))
a=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    if a.same_check(x,y):
        pass
    else:
        a.union(x,y)
count=0
for i in range(n):
    if a.same_check(p_list[i],i+1):
        count=count+1
print(count)

Submission status: Accepted

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


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    par = [i for i in range(0, N + 1)]
    def find_root(i):
        if par[i] != i:
            par[i] = find_root(par[i])
            return par[i]
        return par[i]
    def union(a, b):
        a_ = find_root(a)
        b_ = find_root(b)
        if a_ != b_:
            par[b_] = a_
        return
    for j in range(M):
        union(x[j], y[j])
    #print(par)
    ret = 0
    for i in range(N):
        val = p[i]
        idx = i + 1
        if val == idx or find_root(idx) == find_root(val):
            ret += 1
    print(ret)
    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()