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

sys.setrecursionlimit(10000)
INF = float('inf')


class WeightedUnionFind:
    def __init__(self, nodes):
        """
        :param collections.Iterable nodes:
        """
        self._parents = {k: k for k in nodes}
        self._ranks = {k: 0 for k in nodes}
        self._sizes = {k: 1 for k in nodes}
        # 直近の親からの重み。root なら 0
        self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        # それぞれの root をくっつけたいので root 間の重みに変換
        # x が上、y が下
        w += self.weight(x)
        w -= self.weight(y)

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
            self._weights[x] = 0
            self._weights[y] = w
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            self._weights[x] = -w
            self._weights[y] = 0
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self.weight(y) - self.weight(x)
        return float('inf')


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

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

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

print(ans)

Submission status: Accepted

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
a = []
v = [0 for i in range(n)]

for i in range(n):
    if v[i] == 0:
        connect.append([i])
        a.append([p[i]-1])
        v[i]=1
        stack =[i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if v[l[q][j]]==0:
                    connect[-1].append(l[q][j])
                    a[-1].append(p[l[q][j]]-1)
                    stack.append(l[q][j])
                    v[l[q][j]]=1

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def find(tab, a):
    if tab[a] == -1: return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    pa, pb = (find(tab, a), find(tab, b))
    if pa!=pb:
        tab[pb] = pa

N, M = [int(a) for a in input().split(" ")]
P = [int(v) for v in input().split(" ")]
xys = [[int(a) for a in input().split(" ")] for i in range(M)]

tab = [-1]*N
for x, y in xys:
    union(tab, x-1, y-1)

indices = defaultdict(list)
ps = defaultdict(set)

for i in range(N):
    root = find(tab, i)
    indices[root].append(i+1)
    ps[root].add(P[i])

ans = 0
for root, idxs in indices.items():
    s = ps[root]
    for idx in idxs:
        if idx in s:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
ps = list(map(int, input().split()))
ps = [i-1 for i in ps]
swap =[list(map(int, input().split())) for i in range(M)]
u = UnionFind(N)
for x, y in swap:
    u.union(x-1, y-1)
ans = 0
for i, p in enumerate(ps):
    if u.find(i, p):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):#0~n-1であることに注意
    def __init__(self, size):
        self.parent = [i for i in range(size)]#親の番号を保存
        self.rank = [0 for _ in range(size)]#ランクを保存


    def find(self, x):#根の番号を返す
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            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)
n, m = map(int, input().split())
p=list(map(int, input().split()))
xy=[list(map(int, input().split())) for i in range(m)]    
U=UnionFind(n)
for i in range(m):
    x, y = xy[i]
    U.unite(x-1, y-1)
ans=0
for i in range(n):
    if U.same(p[i]-1, i):
        ans+=1
print(ans)

Submission status: Accepted

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

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
uf = UnionFind()
for x,y in XY:
  uf.unite(x,y)

unions = {}
for i in range(1, N+1):
  unions.setdefault(uf.find_root(i), set()).add(i)
  
answer = 0
for k, s in unions.items():
  for p in s:
    if P[p-1] in s:
      answer +=1
      
print(answer)

Submission status: Accepted

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

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

union = UnionFindTree(N)
for j in range(M): 
    union.unite(*[int(i) for i in input().split()])

res = 0
for i, v in enumerate(inseq, start=1):
    if union.is_same(i, v):
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
inseq=list(map(int, input().split()))
unifier=[[int(i) for i in input().split()] for j in range(M)]

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))

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

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]

    def is_same(self, a, b):
        # print(self.nodes)
        return self.find(a) == self.find(b)

union = UnionFindTree(N)
for i,j in unifier:
    union.unite(i, j)

res = 0
for i, v in enumerate(inseq, start=1):
    if union.is_same(i, v):
        res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class UnionFind:
    def __init__(self, nodes):
        """
        :param collections.Iterable nodes:
        """
        self._parents = {k: k for k in nodes}
        self._ranks = {k: 0 for k in nodes}
        self._sizes = {k: 1 for k in nodes}

    def union(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            # rank が小さい方が下
            if self._ranks[x] > self._ranks[y]:
                self._parents[y] = x
                self._sizes[x] += self._sizes[y]
            else:
                self._parents[x] = y
                self._sizes[y] += self._sizes[x]
                if self._ranks[x] == self._ranks[y]:
                    self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


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

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

ans = 0
for i in range(N):
    if uf.find(P[i]) == uf.find(i + 1):
        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 i in range(M)]


class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * 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:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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


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

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

print(ans)

Submission status: Accepted

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

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

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

    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):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

N,M=map(int,input().split())
p=[int(i)-1 for i in input().split()]
U=[UnionFindNode(i) for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    U[x-1].unite(U[y-1])
ans=0
for i in range(N):
    if U[i].is_group(U[p[i]]):
        ans+=1
print(ans)

Submission status: Accepted

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

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

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

    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):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_

    def same(self, node):
        return self.root() == node.root()


if __name__ == "__main__":
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    uf = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        x, y = map(int, input().split())
        uf[x - 1].unite(uf[y - 1])
    ans = 0
    for i, n in enumerate(p):
        if uf[i].same(uf[n - 1]):
            ans += 1
    print(ans)

Submission status: Accepted

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

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

def find(n):
	if uf[n] == n:
		return n
	uf[n] = find(uf[n])
	return uf[n]

def union(n, m):
	uf[find(n)] = find(m)

def same(n, m):
	return find(n) == find(m)

for _ in range(M):
	union(*map(int, input().split()))

for i in range(N+1):
	find(i)

print(sum([1 if same(i+1,v) else 0 for i,v in enumerate(p)]))

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


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

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

Submission status: Accepted

Solution code:
# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            

n, m = (int(i) for i in input().split())
a = [int(i)-1 for i in input().split()]
xy = [[int(i)-1 for i in input().split()] for i in range(m)]

uf = UnionFind(n)

for x,y in xy: 
    uf.unite(x, y)

cnt = 0
for idx, a_ in enumerate(a):
    if uf.same(idx, a_):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#UnionFind
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 unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    else:
        if rank[x] < rank[y]:
            par[x] = y

        else:
            par[y] = x

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

#main
n, m = map(int,input().split())
p = list(map(int,input().split()))
par = [i for i in range(n)]
rank = [0] * n

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]  # グループ番号
        self.rank = [0 for _ in range(n)]

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

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

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


N, M = map(int, input().split())
p = list(map(int, input().split()))
u = UnionFind(N + 1)
for i in range(M):
    a, b = map(int, input().split())
    u.union(a - 1, b - 1)
c = 0
for i in range(N):
    # print(u.find(i), u.find(p[i]))
    if u.find(i) == u.find(p[i] - 1):
        c += 1
print(c)

Submission status: Accepted

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

ufp = [i for i in range(n)]
ufs = [1 for _ in range(n)]

def root(i):
  pi = i
  while ufp[pi] != pi:
    pi = ufp[pi]
    ufp[pi] = root(pi)
  return pi

def union(i, j):
  pi, pj = root(i), root(j)
  if pi == pj:
    return
  if ufs[pi] < ufs[pj]:
    ufp[pi] = pj
  elif ufs[pj] < ufs[pi]:
    ufp[pj] = pi
  else:
    if pi < pj:
      ufp[pj] = pi
      ufs[pi] += 1
    else:
      ufp[pi] = pj
      ufs[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:
def init(n):
    global par, rank
    par = [i for i in range(n)]
    rank = [0] * n

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

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

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

N, M = map(int, input().split())
init(N)
p = list(map(int, input().split()))
for _ in range(M):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)
ans = 0
for i in range(N):
    if same(i, p[i] - 1):
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

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

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

print(res)

Submission status: Accepted

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

# refered to
# rank : http://at274.hatenablog.com/entry/2018/02/02/173000
# size : abc120 kaisetsu
class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return 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(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 

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

    for i in range(M):
        uf.union(x[i], y[i])

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

    print(ans)

    return


# Generated by 1.1.3 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 = list(map(int,input().split()))
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
par = []
rank = []
for i in range(N):
  par.append(i)
  rank.append(0)
def find(x,par):
  if par[x] == x:
    return x
  else:
    return find(par[x],par)
def unite(x,y,par,rank):
  x = find(x,par)
  y = find(y,par)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
for i in range(M):
  unite(L[i][0]-1,L[i][1]-1,par,rank)
ans = 0
for i in range(N):
  if find(P[i]-1,par) == find(i,par):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if 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 = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

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

print(ans)

Submission status: Accepted

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

t = {p:p for p in ps}

def trace(x):
    route = [x]
    while t[x] != x:
        x = t[x]
        route.append(x)
    for v in route:
        t[v] = route[-1]
    return route

for x, y in xys:
    u = trace(x)[-1]
    v = trace(y)[-1]
    if u!=v:
        t[u] = v

avs = [
    p
    for i, p in enumerate(ps)
    if trace(i+1)[-1] == trace(p)[-1]
]

print(len(avs))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
k=[i for i in range(n+1)]
r=[0]*(n+1)
def root(x):
    if x==k[x]:
        return x
    x=k[x]
    return root(k[x])
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if r[x]>r[y]:
            k[y]=x
            r[x]+=1
        else:
            k[x]=y
            r[y]+=1
c=0
for i in range(m):
    x,y=map(int,input().split())
    unite(x,y)
for i in range(n):
    if root(i+1)==root(p[i]):
        c+=1
print(c)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_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.union(x-1, y-1)
ans = 0
for i in range(n):
  if uf.is_same(i, p[i] - 1):
    ans += 1
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return 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(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 

def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(x[i], y[i])
    
    ans = 0
    for i in range(N):
        if(uf.same_check(p[i], i+1)):
            ans += 1

    # rootl = [i for i in range(1,N+1) if uf.par[i] < 0]

    # ans = 0
    # for i in rootl:
    #     # そえじちゅーしゅつ
    #     tl = {j for j in range(1,N+1) if uf.same_check(i,j)} 
    #     # なかみちぇっく
    #     il = {p[j-1] for j in tl}
    #     # たしあわせ
    #     ans += len(tl & il)

    print(ans)
    return


# Generated by 1.1.3 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()