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
sys.setrecursionlimit(10 ** 7)


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 = list(map(int, input().split()))
    uf = UF_tree(N + 10)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)

    ans = sum(uf.isSame(i, p) for i, p in enumerate(P, start=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)]

parent = list(range(N))

def root(arg):
    if arg == parent[arg]:
        return arg
    else:
        ret = root(parent[arg])
        parent[arg] = ret
        return ret

def unite(src, dst):
    r_src = root(src)
    r_dst = root(dst)
    #
    if r_src != r_dst:
        parent[r_src] = r_dst

for xi, yi in xy:
    unite(xi - 1, yi - 1)

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

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)

for x,y in XY:
    x,y = x-1,y-1
    if not uf.is_same(x,y):
        uf.unite(x,y)
ans = 0
for i,p in enumerate(P):
    if uf.is_same(i,p-1):
        ans += 1
print(ans)

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 = list(map(int, input().split()))
tree = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    tree.union(a - 1, b - 1)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

    n,m = LI()
    p = LI()
    f = [None]*n
    for i in range(n):
        p[i] -= 1
        f[p[i]] = i
    par = [i for i in range(n)]
    rank = [0]*n
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        if root(a) != root(b):
            unite(a,b)
    ans = 0
    for i in range(n):
        if root(f[i]) == root(i):
            ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

n, m = map(int, input().split())
P = list(map(int, input().split()))
P = [p-1 for p in P]
def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

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

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

par = [-1]* n
rank = [0]*n

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

ans = 0
for i, p in enumerate(P):
    if Same(i, p, par):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#-----UnionFind-----(0-indexed)
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(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
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n,m=map(int,input().split())
p=list(map(int,input().split()))
u=UnionFind(n)
for _ in range(m):
  x,y=map(int,input().split())
  u.unite(x-1,y-1)
ans=0
for i in range(n):
  if u.root_same(i,p[i]-1):ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(i, g, visited):
  visited.add(i)
  for j in g[i]:
    if not (j in visited):
      dfs(j, g, visited)

def main():
  n, m = map(int, input().split())
  p = (list(map(int, input().split())))
  g = [[] for i in range(n + 1)]
  for i in range(m):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
  seen = [False for i in range(n + 1)]
  ans = 0
  for i in range(1, n):
    if not seen[i]:
      visited = set()
      dfs(i, g, visited)
      for j in visited:
        seen[j] = True
        if p[j - 1] in visited:
          ans += 1
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# from collections import deque
# from heapq import heapify,heappop,heappush,heappushpop
# from copy import copy,deepcopy
# from itertools import permutations,combinations
# from collections import defaultdict,Counter
# from pprint import pprint

def myinput():
    return map(int,input().split())

# def mycol(data,col):
#     return [ row[col] for row in data ]

# def mysort(data,col):
#     data.sort(key=lambda x:x[col],reverse=False)
#     return data

# def mymax(data):
#     M = -1*float("inf")
#     for i in range(len(data)):
#         m = max(data[i])
#         M = max(M,m)
#     return M

# def mymin(data):
#     m = float("inf")
#     for i in range(len(data)):
#         M = min(data[i])
#         m = min(m,M)
#     return m

class UnionFind():
    # parentsは「要素が根の場合に"そのグループの要素数*(-1)"を格納するリスト」
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    # 要素xが属するgroupの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    # 要素xが属するgroupと要素yが属するgroupを併合する
    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
    # 要素xが属するgroupのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    # 要素x,yが同じgroupに属するかをTrueかFalseで返す
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するgroupに属する要素をリストで返す
    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]
    # groupの数を返す
    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 = myinput()
p = list(myinput())
xy = [ list(myinput()) for _ in range(m) ]

uf = UnionFind(n)

for i in range(m):
    x = xy[i][0] - 1
    y = xy[i][1] - 1
    uf.union(x,y)

count = 0
for i in range(n):
    tmp = p[i] - 1
    if tmp==i:
        pass
    else:
        if uf.same(i,tmp):
            pass
        else:
            count += 1
            
# print(count)
ans = n - count
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, y):
        return - self.parents[self.find(x)]

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

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

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

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

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


N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
union_find = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    union_find.union(x-1, y-1)
d = {}
for i in range(N):
    d[P[i]] = i
ans = 0
for i in range(N):
    if union_find.same(i, d[i]):
        ans += 1
print(ans)

Submission status: Accepted

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

    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

uni = UnionFind(n)

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

ret = 0

tmp_dict = dict()

for i in range(n):
    parent = uni.find(i)
    if parent in tmp_dict:
        tmp_dict[parent].append(i)
    else:
        tmp_dict[parent] = [i]

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = set()
    for var in t_list:
        tmp.add(q_list[var])
    ret += len(tmp & set(t_list))

print(ret)

Submission status: Accepted

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

uf = {i:i for i in range(1,n+1)}

def get_parent(i):
  lst = []
  while uf[i] != i:
    lst.append(i)
    i = uf[i]
  for l in lst[:-1]:
    uf[l] = i
  return i

def unite(i,j):
  p = get_parent(i)
  uf[get_parent(j)] = p

def same(i,j):
  return get_parent(i) == get_parent(j)

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

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

Submission status: Accepted

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

uf = {i:i for i in range(1,n+1)}

def get_parent(i):
  lst = []
  while uf[i] != i:
    lst.append(i)
    i = uf[i]
  for l in lst[:-1]:
    uf[l] = i
  return i

def unite(i,j):
  p = get_parent(i)
  uf[get_parent(j)] = p

def same(i,j):
  return get_parent(i) == get_parent(j)

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

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

Submission status: Accepted

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

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

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


def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = []
    for i in range(n):
        g.append([p[i], i])
    g.sort()  # p[i]でsort()している

    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 uf.same(i, g[i][1]):  # インデックスと数の親が仁いい場合は+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()))
uf = {i:-1 for i in range(1,n+1)}

def get_p(i):
  while uf[i] != i:
    if uf[i] == -1:
      return i
    i = uf[i]
  return i

for _ in range(m):
  x,y = map(int,input().split())
  if x > y:
    x,y = y,x
  if uf[x]== uf[y] == -1:
    uf[x] = x
    uf[y] = x
  elif uf[x] != -1 and uf[y] != -1:
    p = get_p(x)
    uf[x] = p
    index = y
    while index != uf[index]:
      index = uf[y]
      uf[y] = p
      y = index
    else:
      uf[index] = p
  else:
    if uf[x] == -1:
      p = get_p(y)
    else:
      p = get_p(x)
    uf[x] = p
    uf[y] = p

ans = 0  
for i, p in enumerate(P):
  if get_p(i+1) == get_p(p):
    ans += 1
print(ans)

Submission status: Accepted

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


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]


n,m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n+1)]
cnt = [1 for _ in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    aa = get_par(par, a)
    bb = get_par(par, b)
    if aa == bb:
        continue
    # unite
    if cnt[aa] > cnt[bb]:
        par[bb] = aa
        cnt[aa] += cnt[bb]
    else:
        par[aa] = bb
        cnt[bb] += cnt[aa]

ans = 0
for i in range(n):
    a = p[i]
    if get_par(par, a) == get_par(par, i+1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!python3

# input
N, M = list(map(int, input().split()))
P = [None] + list(map(int, input().split()))
X, Y = [None] * M, [None] * M
for i in range(M):
    X[i], Y[i] = list(map(int, input().split()))


def main():
    S = [{i} for i in range(N + 1)]
    G = list(range(N + 1))
    for i in range(M):
        g1, g2 = G[X[i]], G[Y[i]]
        if g1 == g2:
            continue
        if len(S[g1]) < len(S[g2]):
            g1, g2 = g2, g1
        S[g1] |= S[g2]
        for j in S[g2]:
            G[j] = g1

    visit = [False] * (N + 1)
    ans = 0
    for i in range(1, N + 1):
        if visit[i]:
            continue
        s = S[G[i]]
        for j in s:
            visit[j] = True
            if P[j] in s:
                ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.par  = [i for i in range(self.N)]
        self.rank = [0 for _ in range(self.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[x] = y
        else:
            self.par[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)


N, M = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
ind = {pi : i + 1 for i, pi in enumerate(p)}
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):
    if i == ind[i] or uf.same(i, ind[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

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

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

    ans = 0
    for i,j in enumerate(p):
        ans += uf.same(i, j-1)
    print(ans)
main()

Submission status: Accepted

Solution code:
class UnionFind():
    '''
    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 count(self, x):
        return -self.root[self.find_root(x)]

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

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

set_list = [set() for _ in range(N)]

for i in range(N):
    root = union_find.find_root(i)
    set_list[root].add(p[i])

ans = 0
for i in range(N):
    if (i+1) in set_list[union_find.find_root(i)]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  lp = list(map(int, input().split()))
  
  luf = [-1] * (n)
  def find(x):
    if luf[x] < 0:
      return x
    else:
      luf[x] = find(luf[x])
      return luf[x]
  
  def union(x, y):
    px, py = find(x), find(y)
    if px == py:
      return
    if px < py:
      px, py = py, px
    luf[px] += luf[py]
    luf[py] = px

  
  for _ in range(m):
    x, y = map(int, input().split())
    union(x-1, y-1)
  
  dic = dict()
  for i, p in enumerate(lp):
    p -= 1
    pp = find(p)
    if pp in dic:
      dic[pp]['inds'] |= set([i])
      dic[pp]['vals'] |= set([p])
    else:
      dic[pp] = dict()
      dic[pp]['inds'] = set([i])
      dic[pp]['vals'] = set([p])
  print(sum([len(v['inds'] & v['vals']) for _, v in dic.items()]))
    

if __name__=='__main__':
  main()

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(N)

for i in range(M):
    node1, node2 = map(int, input().split())
    uf.union(node1 - 1, node2 - 1)

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

Submission status: Accepted

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


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())
p = list(map(int, input().split()))
uf = UnionFind(n + 1)
cnt = 0
for i in range(m):
    x, y = map(int, input().split())
    uf.union(x, y)
for i in range(n):
    if uf.same(i + 1, p[i]):
        cnt += 1
print(cnt)

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)


n, m = map(int, input().split())
p = 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 i, p_i in enumerate(p):
    if uf.same(i, p_i-1):
        ans += 1

print(ans)