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


class Node:
    def __init__(self, index):
        self.index = index
        self.connected_indices = set()


def build_graph(nodes, curr_index, connected_indices, reached_indices):
    # already reached
    if curr_index in connected_indices or curr_index in reached_indices:
        return

    connected_indices |= {curr_index}
    reached_indices |= {curr_index}

    unreached_indices = nodes[curr_index].connected_indices - connected_indices

    for i in unreached_indices:
        build_graph(nodes, i, connected_indices, reached_indices)

    return connected_indices


if __name__ == '__main__':
    N, M = map(int, input().split())
    p = [int(v) - 1 for v in input().split()]

    nodes = [Node(i) for i in range(N)]
    for _ in range(M):
        xy_str = input().split()
        x, y = int(xy_str[0]) - 1, int(xy_str[1]) - 1

        # link neighbors
        nodes[x].connected_indices |= {y}
        nodes[y].connected_indices |= {x}

    reached_indices = set()
    all_connected_indices = [None] * N
    for i in range(N):
        connected_indices = build_graph(nodes, i, set(), reached_indices)
        if connected_indices is None:
            continue

        for c in connected_indices:
            all_connected_indices[c] = connected_indices

    answer = sum([p[i] in all_connected_indices[i] for i in range(N)])
    print(answer)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2000000000)


class Node:
    def __init__(self, index):
        self.index = index
        self.connected_indices = set()

    def __repr__(self):
        return '{}: {}'.format(self.index, self.connected_indices)


def build_graph(nodes, curr_index, connected_indices, reached_indices):
    # already reached
    if curr_index in connected_indices or curr_index in reached_indices:
        return

    connected_indices |= {curr_index}
    reached_indices |= {curr_index}

    unreached_indices = nodes[curr_index].connected_indices - connected_indices

    for i in unreached_indices:
        build_graph(nodes, i, connected_indices, reached_indices)

    return connected_indices


# if True:
#     line_index = 0
#
#
#     def input():
#         global line_index
#         lines = ['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']
#
#         line = lines[line_index]
#         line_index += 1
#         return line

if __name__ == '__main__':
    N, M = map(int, input().split())
    p = [int(v) - 1 for v in input().split()]

    nodes = [Node(i) for i in range(N)]
    for _ in range(M):
        xy_str = input().split()
        x, y = int(xy_str[0]) - 1, int(xy_str[1]) - 1

        nodes[x].connected_indices |= {y}
        nodes[y].connected_indices |= {x}

    reached_indices = set()
    all_connected_indices = [None] * N
    for i in range(N):
        connected_indices = build_graph(nodes, i, set(), reached_indices)
        if connected_indices is None:
            continue

        for c in connected_indices:
            all_connected_indices[c] = connected_indices

    answer = sum([p[i] in all_connected_indices[i] for i in range(N)])
    print(answer)
    # print(desirable_swaps)
    # print(nodes)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)

global visited,num,graph

def dfs(subtree):
    global visited,num,graph
    if visited[subtree] != 0:
        return

    visited[subtree] = num
    for node in graph[subtree]:
        if visited[node] != 0:
            continue
        dfs(node)

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

starting = list(map(int,input().split()))
graph = [[] for x in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [0 for x in range(N+1)]
num = 1
for i in range(1,N+1):
    if visited[i] == 0:
        dfs(i)
        num += 1

ans = 0
for i in range(1,N+1):
    if visited[i] == visited[starting[i-1]]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def d_equals(N, M, P, S):
    class UnionFind(object):
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の親(parent)はi番
            self.rank = [0] * N  # 初期状態では全頂点がランク0(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):  # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    p = [0] + P
    ans = 0
    uf = UnionFind(N + 1)
    for a, b in S:
        uf.union(a, b)  # Pのa番とb番は繋がっている
    for i in range(1, N + 1):
        if uf.is_same(p[i], i):
            # 2つが同じ連結成分に属するなら何回かswapしてp_i=iにできる
            # 最初からp_i=iの場合、unionしてなくてもこの条件は成立
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(M)]
print(d_equals(N, M, P, S))

Submission status: Accepted

Solution code:
def d_equals(N, M, P, S):
    class UnionFind(object):
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の親(parent)はi番
            self.rank = [0] * N  # 初期状態では全頂点がランク0(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

    ans = 0
    uf = UnionFind(N)
    for a, b in S:
        uf.union(a - 1, b - 1)  # Pのa番とb番は繋がっている(0-indexed)
    for i in range(N):
        if uf.is_same(P[i] - 1, i):
            # 2つが同じ連結成分にあるなら、何回かswapしてp_i=iにできる
            # 最初からp_i=iの場合、unionしてなくてもこの条件は成立
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(M)]
print(d_equals(N, M, P, S))

Submission status: Accepted

Solution code:
def d_equals(N, M, P, S):
    class UnionFind(object):
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の親(parent)はi番
            self.rank = [0] * N  # 初期状態では全頂点がランク0(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):  # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    ans = 0
    uf = UnionFind(N)
    for a, b in S:
        uf.union(a - 1, b - 1)  # Pのa番とb番は繋がっている(0-indexed)
    for i in range(N):
        if uf.is_same(P[i] - 1, i):
            # 2つが同じ連結成分にあるなら、何回かswapしてp_i=iにできる
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(M)]
print(d_equals(N, M, P, S))

Submission status: Accepted

Solution code:
def d_equals(N, M, P, S):
    class UnionFind(object):
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の親(parent)はi番
            self.rank = [0] * N  # 初期状態では全頂点がランク0(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):  # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    ans = 0
    uf = UnionFind(N)
    for a, b in S:
        uf.union(a - 1, b - 1)  # Pのa番とb番は繋がっている(0-indexed)
    for i in range(N):
        if uf.is_same(P[i] - 1, i):
            # 2つが同じ連結成分にあるなら、何回かswapしてp_i=iにできる
            ans += 1
        elif P[i] - 1 == i:
            # 同じ連結成分には属していないが、最初からp_i=iだった
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(M)]
print(d_equals(N, M, P, S))

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M=map(int, raw_input().split())
p=map(int, raw_input().split())

#print "p:",p

a = []
for i in range(M):
	x,y=map(int,raw_input().split())
	if x<=y: a.append((x-1,y-1))
	else: a.append((y-1,x-1))

a=sorted(a, key=lambda x: x[0])


#Union Find
par=[ i for i in range(N) ]

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

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


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


for x,y in a:
	if not same(x,y):
		unite(x,y)


ans=0
for idx,i in enumerate(p):
	if same(idx,i-1):
		ans+=1
print ans

Submission status: Accepted

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

n, m = map(int, input().split())
p = [int(i) for i in input().split()]
pairs = [[int(i) for i in input().split()] for _ in range(m)]

parents = [i for i in range(n + 1)]

def ufRoot(a):
    global parents
    if parents[a] == a:
        return(a)
    else:
        parents[a] = ufRoot(parents[a])
        return parents[a]

def ufFind(a, b):
    return ufRoot(a) == ufRoot(b)

def ufUnite(a, b):
    global parents
    a = ufRoot(a)
    b = ufRoot(b)
    if (a == b):
        return
    parents[a] = b

for pp in pairs:
    if ufFind(pp[0], pp[1]) == False:
        ufUnite(pp[0], pp[1])

for i in range(len(parents)):
    parents[i] = ufRoot(parents[i])


uniques = list(set(parents))
dict_ids = {}
dict_values = {}

for u in uniques:
    dict_ids[u] = []
    dict_values[u] = []

for i in range(n):
    dict_ids[parents[i + 1]].append(i + 1)
    dict_values[parents[i + 1]].append(p[i])

res = 0
for u in uniques:
    sets = set(dict_ids[u]).intersection(dict_values[u])
    res += len(sets)

print(res)

Submission status: Accepted

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

par = [i for i in range(0, n+1)]

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

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

for i in x:
    a, b = i
    unite(a, b)

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

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
idx = [0]*(n+1)
for i, v in enumerate(p, 1):
    idx[v] = i
par = list(range(n+1))
sz = [1]*(n+1)
def union(i, j):
    i = find(i)
    j = find(j)
    if sz[i] > sz[j]:
        i, j = j, i
    par[i] = par[j]
    sz[j] += sz[i]
def find(i):
    if par[i] == i:
        return i
    par[i] = find(par[i])
    return par[i]
for _ in range(m):
    x, y = map(int, input().split())
    union(x, y)
print(sum(find(idx[i]) == find(i) for i in range(1, n+1)))

Submission status: Accepted

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    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 = [int(i) for i in input().split()]
p = [int(i) - 1 for i in input().split()]

uf = UnionFind3(N + 1)
for i in range(M):
    x, y = [int(i)-1 for i in input().split()]
    uf.union(x, y)

count = 0
for i in range(N):
    if p[i] != i:
        if uf.find(p[i]) == uf.find(i):
            count += 1
            # pi = p[i]
            # ppi = p[pi]
            # p[i], p[pi] = ppi, pi
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    ans = 0
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    uf = UnionFind(n+1)
    for i in range(m):
        a,b = map(int,input().split())
        uf.union(a-1,b-1)
    for i in range(n):
        if uf.find(s[i]-1,i):
            ans += 1
        elif s[i]-1  == i :
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().strip().split()]
par = list(range(n))
rank = [0]*n

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

def unite(x,y):
  x,y = map(find, (x,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)

p = [int(x) for x in input().strip().split()]
for _ in range(m):
  x,y = [int(z)-1 for z in input().strip().split()]
  unite(x,y)

p = sorted([(z,i) for i,z in enumerate(p)], reverse=True)
print(sum([same(val-1,idx) for val,idx in p]))

Submission status: Accepted

Solution code:
import collections
n,m = map(int,input().split())
p = list(map(int,input().split()))
base = 0
basemap = []
for i in range(n):
	if (i+1) == p[i]:
		base += 1
		basemap.append(i+1)

branch = dict()
for i in range(1,n+1):
	branch[i] = []

for i in range(m):
	x,y = map(int,input().split())
	branch[x].append(y)
	branch[y].append(x)
compare = [0 for i in range(n+1)]
for i in range(1,n+1):
	if branch[i] != []:
		compare[i] = 1

arrival = [0 for i in range(n+1)]
ans = []
q = []

ind = 1
while arrival != compare:
	counter = base
	while not(arrival[ind] == 0 and compare[ind] == 1):
		ind += 1
	q.append(ind)
	arrival[ind] = 1
	section = [q[0]]
	while len(q) > 0:
		next = branch[q[0]]
		for i in range(len(next)):
			if arrival[next[i]] == 0:
				section.append(next[i])
				arrival[next[i]] = 1
				q.append(next[i])
		q.pop(0)
	psec = []
	for i in range(len(section)):
		psec.append(p[section[i]-1])
	t = section + psec + basemap
	search = collections.Counter(t)
	for i in search:
		if search[i] == 2:
			 counter += 1
	ans.append(counter)
print(max(ans))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    p = map(int, input().split())
    trans = []

    for _ in range(m):
        x, y = map(int, input().split())
        trans.append((x, y))
    
    ss = dict()

    for t in trans:
        x, y = t
        xs = ss.get(x, None)
        ys = ss.get(y, None)

        if xs is None and ys is None:
            zs = set([x, y])
            ss[x] = zs
            ss[y] = zs
        elif xs is not None and ys is None:
            xs.add(y)
            ss[y] = xs
        elif xs is None and ys is not None:
            ys.add(x)
            ss[x] = ys
        else:
            if id(xs) == id(ys):
                continue

            if len(xs) >= len(ys):
                for yy in ys:
                    ss[yy] = xs
                    xs.add(yy)
            else:
                for xx in xs:
                    ss[xx] = ys
                    ys.add(xx)

    c = 0
    for i, v in enumerate(p, 1):
        if i == v:
            c += 1
        elif i in ss and v in ss[i]:
            c += 1
    print(c)

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = list(map(lambda x: int(x) -1 , input().split()))
class UnionFind:
    def __init__(self, n):
        self.data = [-1] * n
    def union(self, x, y):
        x,y = self.root(x), self.root(y)
        if x != y :
            if self.data[y] < self.data[x]:
                x,y = y,x
            self.data[x] += self.data[y]
            self.data[y] = x
        return x != y
    def root(self, x):
        if self.data[x] < 0 :
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    def findSet(self, x, y):
        return self.root(x) == self.root(y)
uf = UnionFind(N)
for _ in range(M):
    px,py = map(int, input().split())
    px -= 1
    py -= 1
    uf.union(px,py)
ans = 0
for i, v in enumerate(p):
    ans += 1 if uf.findSet(v,i) else 0
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))


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: Runtime Error

Solution code:
from logging import root
from tokenize import group
import numpy
from pandas.core.resample import f
from regex.regex import U

class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

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

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

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

    def size(self, i):
        return -self.parent[self.root(i)]

N, M = map(int, input().split())
p = [int(i) - 1 for i in input().split()]

forest = UnionFind(N)

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

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

print(ans)

Submission status: Runtime Error

Solution code:
class uft():
    def __init__(self,n):
        self.p=[ -1 for i in range(n)]
        self.r=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
            
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
            
        if(x!=y):
            self.p[x]=y
        return
    
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
for i in range(n):
    if(uf.find(i)==uf.find(p[i])):
        ans+=1
        
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(m):
        if f[m]:
            return set()
        f[m] = 1
        tmp = nb[m]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        st = Q(i)
        if len(st) == 0:
            continue

        for k in list(st):
            gr[k] = c
        c += 1

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if x == i:
            ans += 1
            continue
        a = gr[x]
        b = gr[i]
        if a == -1 or b == -1:
            continue
        elif a == b:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]
    *r, = range(1,n+1)
    if p == r:
        print(n)
        exit()
    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return set()
        f[i] = 1
        tmp = nb[i]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        st = Q(i)
        if len(st) == 0:
            continue

        for k in list(st):
            gr[k] = c
        c += 1

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if x == i:
            ans += 1
            continue
        a = gr[x]
        b = gr[i]
        if a == -1 or b == -1:
            continue
        elif a == b:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return set()
        f[i] = 1
        tmp = nb[i]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        st = Q(i)
        if len(st) == 0:
            continue

        for k in list(st):
            gr[k] = c
        c += 1

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if x == i:
            ans += 1
            continue
        a = gr[x]
        b = gr[i]
        if a == -1 or b == -1:
            continue
        elif a == b:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return set()
        f[i] = 1
        tmp = nb[i]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        st = Q(i)
        if len(st) == 0:
            gr[i] = c
            continue
        for k in list(st):
            gr[k] = c
        c += 1

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if gr[x] == gr[i]:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return set()
        f[i] = 1
        tmp = nb[i]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        c += 1
        st = Q(i)
        if len(st) == 0:
            continue

        for j in list(st):
            gr[j] = c

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if gr[x] == gr[i]:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return []
        f[i] = 1
        tmp = nb[i]
        for j in tmp:
            tmp += Q(j)
        return tmp

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        c += 1
        gp = nb[i]
        tm = sum([Q(j) for j in gp],[])
        if len(tm) == 0:
            continue
        st = set(tm)
        for j in list(st):
            gr[j] = c

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if gr[x] == gr[i]:
           ans += 1

    print(ans)

if __name__ == '__main__':
    main()