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

Solution code:
class Unionfind():  # 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 all_group_members(self):  # グループごとの辞書
        members_dict = {i: set([i])
                        for i, x in enumerate(self.parents) if x < 0}
        for i, x in enumerate(self.parents):
            members_dict[self.find(x)].add(i)
        return members_dict


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.all_group_members().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.rstrip())
ns = lambda: map(int, sys.stdin.rstrip().split())
na = lambda: list(map(int, sys.stdin.rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.rstrip().split()))


# ===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):
        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())


def main():
    n, m = ns()
    p = na()
    p_idx = {pi - 1: i for i, pi in enumerate(p)}

    uf = UnionFind(n)

    for _ in range(m):
        x, y = ns()
        uf.union(x - 1, y - 1)

    ans = 0
    for l in uf.all_group_members().values():
        base = set(l)
        for m in l:
            if p_idx[m] in base:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1]*n

    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u==v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u
        self.size[v] += self.size[u]
        self._par[u] = v

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

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

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

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
p=list(map(int,input().split()))
from collections import defaultdict
c=0
for i in range(n):
    if p[i]==i+1:
        c+=1
vis=[0]*n
def dfs(x):
    vis[x]=1
    a.add(x+1)
    for u in d[x]:
        if vis[u]==0:
            dfs(u)
d=defaultdict(list)
for i in range(m):
    a,b=list(map(int,input().split()))
    d[a-1].append(b-1)
    d[b-1].append(a-1)
ans=0
for i in range(n):
    if vis[i]==0:
        a=set()
        dfs(i)
        l=0
        z=0
        for j in a:
            if p[j-1] in a:
                z+=1
            if p[j-1]==j:
                l+=1
        ans=max(ans,c+z-l)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
p=list(map(int,input().split()))
from collections import defaultdict
c=0
for i in range(n):
    if p[i]==i+1:
        c+=1
vis=[0]*n
def dfs(x):
    vis[x]=1
    a.append(x+1)
    for u in d[x]:
        if vis[u]==0:
            dfs(u)
d=defaultdict(list)
for i in range(m):
    a,b=list(map(int,input().split()))
    d[a-1].append(b-1)
    d[b-1].append(a-1)
ans=0
for i in range(n):
    if vis[i]==0:
        a=[]
        dfs(i)
        l=0
        z=0
        for j in a:
            if p[j-1] in a:
                z+=1
            if p[j-1]==j:
                l+=1
        ans=max(ans,c+z-l)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
p=list(map(int,input().split()))
from collections import defaultdict
c=0
for i in range(n):
    if p[i]==i+1:
        c+=1
vis=[0]*n
def dfs(x):
    vis[x]=1
    a.append(x+1)
    for i in d[x]:
        if vis[i]==0:
            dfs(i)
d=defaultdict(list)
for i in range(m):
    a,b=list(map(int,input().split()))
    d[a-1].append(b-1)
    d[b-1].append(a-1)
ans=0
for i in range(n):
    if vis[i]==0:
        a=[]
        dfs(i)
        l=0
        z=0
        for i in a:
            if p[i-1] in a:
                z+=1
            if p[i-1]==i:
                l+=1
        ans=max(ans,c+z-l)
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)
union = uf.union
find = uf.find


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

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

print(ans)

Submission status: Runtime Error

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

par = {x:x for x in range(1, n+1)}

def root(node):
    if par[node] == node:
        return node
    par[node] = root(par[node])
    return par[node]

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

print(ans)

Submission status: Runtime Error

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

par = {x:x for x in range(1, n+1)}

def root(node):
    if par[node] == node:
        return node
    par[node] = root(par[node])
    return par[node]

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(pow(10,9))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.find(self.root[x])
    def union(self,x,y):
        x,y = self.find(x),self.find(y)
        if self.rank[x]<self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.root[y] = x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(pow(10,6))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x]==-1:
            return x
        else:
            return self.find(self.root[x])
    def union(self,x,y):
        root_x,root_y = self.find(x),self.find(y)
        if self.rank[root_x]<self.rank[root_y]:
            root_x,root_y = root_y,root_x
        self.rank[root_x] += self.rank[root_y]
        self.root[root_y] = root_x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x]==-1:
            return x
        else:
            return self.find(self.root[x])
    def union(self,x,y):
        root_x,root_y = self.find(x),self.find(y)
        if self.rank[root_x]<self.rank[root_y]:
            root_x,root_y = root_y,root_x
        self.rank[root_x] += self.rank[root_y]
        self.root[root_y] = root_x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        C = [i]
        hist[i]=1
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    C.append(y)
                    hist[y]=1
        C = sorted(C)
        A.append(C)
cnt = 0
for C in A:
    B = []
    for c in C:
        B.append(P[c])
    B = sorted(B)
    cur = 0
    for i in range(len(C)):
        if C[i]==B[cur]:
            cnt += 1
            cur += 1
        elif C[i]<B[cur]:
            continue
        elif C[i]>B[cur]:
            while C[i]>B[cur]:
                cur += 1
            if B[cur]==C[i]:
                cnt += 1
            else:
                continue
print(cnt)

Submission status: Runtime Error

Solution code:
import queue
n,m = map(int,input().split())
pi = [int(i) for i in input().split()]

xy = [[] for j in range(n+1)]

for i in range(m):
    x,y = map(int,input().split())
    xy[x].append(y)
    xy[y].append(x)
    
path = [[] for i in range(n+1)]
#check = [0] * (n+1)

check = [-1]*(n+1)

def dfs(x,check):
    #if check[x] != -1:
    #    return
    for i in range(len(xy[x])):
        cho = xy[x][i]
        #print(cho,x)
        if check[cho] != -1:
            continue
        check[cho] = num
        dfs(cho,check)
    
    return

num = 0
for i in range(1,n+1):
    #print(i,check[i])
    if check[i] != -1:
        continue
    if len(xy[i]) == 0:
        continue
    dfs(i,check)
    num += 1
#print(check)
ans = 0

for i in range(1,n+1):
    if pi[i-1] == i:
        ans += 1
    elif check[i] == check[pi[i-1]]:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:

n,m=map(int,input().split())
root=[i for i in range(n+1)]
rank=[0]*(n+1)
def find(x):
    if x==root(x):
        return x 
    else:
        return find(root[x])

def union(x,y):
    x=find(x)
    y=find(y)
    if rank[x]>rank[y]:
        root[y]=x 
    else rank[x]<rank[y]:
        root[x]=y
        if rank[x]==rank[y]:
            rank[y]+=1
def k_sub():
    
    p=list(map(int,input().split()))
    p=[-1]+p 
    for _ in range(m):
        x,y=map(int,input().split())
        union(x,y)
    d=[[] for i in range(n+1)]
    u=[[] for i in range(n+1)]
    for i in range(1,n+1):
        d[find[i]].append(i)
        u[find[i]].append(p[i])
    cnt=0
    for i in range(n):
        for candidate in d[i]:
            if candidate in u[i]:
                cnt+=1
    print(cnt)
if __name__=='__main__':
    k_sub()

Submission status: Runtime Error

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

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

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

uf = {i+1:i+1 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(uf,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: Runtime Error

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]):
        cnt += 1
print(cnt)

Submission status: Runtime Error

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 = 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]):
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
class unionFind:
    def __init__(self, n):
        self.data = [-1] * (n+10)

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

    def unite(self, x, y):
        a, b = self.find(x), self.find(y)
        if a!=b:
            self.data[b] += self.data[a]
            self.data[a] = b


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.unite(p[x-1], p[y-1])

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

Submission status: Runtime Error

Solution code:
class unionFind:
    def __init__(self, n, p):
        self.data = [-1] * n

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

    def unite(self, x, y):
        a, b = self.find(x), self.find(y)
        if a!=b:
            self.data[b] += self.data[a]
            self.data[a] = b


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

tree = unionFind(n, p)
for i in range(m):
    x, y = map(int, input().split())
    tree.unite(p[x-1]-1, p[y-1]-1)

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

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split()) 
P=list(map(int,input().split()))
par=[i for i in range(N+1)]
rank=[0]*(N+1)

#根を探す
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:
    return 0
  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):
  a,b=map(int,input().split())
  union(a,b)


print(par)
print(rank)     
  
ans=0
for i in range(1,N+1):
  print(i,P[i-1])
  if same(P[i-1],i):
    ans+=1
print(ans)

Submission status: Runtime Error

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):
        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 r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
u=UnionFind(n)
ans=0
p=list(map(lambda x:int(x-1),input().split()))
for i in range(m):
  a,b=map(lambda x:x-1,map(int,input().split()))
  u.union(a,b)
for i in range(n):
  if u.same(i,p[i]):
    ans+=1
print(ans)

Submission status: Runtime Error

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

class UnionFind():
	def __init__(self, n):
		self.size = n
		self.root = [-1 for _ in range(n+1)]
		self.rnk = [0 for _ in range(n+1)]

	def findRoot(self, a):
		if self.root[a] < 0:
			return a
		else:
			return self.findRoot(self.root[a])

	def uniteTree(self, a, b):
		a = self.findRoot(a)
		b = self.findRoot(b)

		if a == b:
			return

		elif self.rnk[a] > self.rnk[b]:
			self.root[a] += self.root[b]
			self.root[b] = a

		elif self.rnk[b] > self.rnk[a]:
			self.root[b] += self.root[a]
			self.root[a] = b

		elif self.rnk[a] == self.rnk[b]:
			self.root[b] += self.rnk[a]
			self.root[a] = b
			self.rnk[b] += 1

	def judgeTree(self, a, b):
		return self.findRoot(a) == self.findRoot(b)

	def count(self, a):
		return self.rnk[self.findRoot(a)] * (-1)



N, M = map(int, input().split())
A = list(map(int, input().split()))
O = [list(map(int, input().split())) for _ in range(M)]

ope = UnionFind(N)

for i in range(M):
	ope.uniteTree(O[i][0], O[i][1])

cnt = 0
for i in range(N):
	if ope.judgeTree(A[i], i+1):
		cnt += 1

print(cnt)

Submission status: Runtime Error

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

class UnionFind():
	def __init__(self, n):
		self.size = n
		self.root = [-1 for _ in range(n+1)]
		self.rnk = [0 for _ in range(n+1)]

	def findRoot(self, a):
		if self.root[a] < 0:
			return a
		else:
			return self.findRoot(self.root[a])

	def uniteTree(self, a, b):
		a = self.findRoot(a)
		b = self.findRoot(b)

		if a == b:
			return

		elif self.rnk[a] > self.rnk[b]:
			self.root[a] += self.root[b]
			self.root[b] = a

		elif self.rnk[b] > self.rnk[a]:
			self.root[b] += self.root[a]
			self.root[a] = b

		elif self.rnk[a] == self.rnk[b]:
			self.root[b] += self.rnk[a]
			self.root[a] = b
			self.rnk[b] += 1

	def judgeTree(self, a, b):
		return self.findRoot(a) == self.findRoot(b)

	def count(self, a):
		return self.rnk[self.findRoot(a)] * (-1)



N, M = map(int, input().split())
A = list(map(int, input().split()))
O = [list(map(int, input().split())) for _ in range(M)]

ope = UnionFind(N)

for i in range(M):
	ope.uniteTree(O[i][0], O[i][1])

cnt = 0
for i in range(N):
	if ope.judgeTree(A[i], i+1):
		cnt += 1

print(cnt)

Submission status: Runtime Error

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

uf = uf(N)

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

count = 0
for n in range(N):
    if uf.is_same_group(P[n-1],n+1):
        count += 1

print(count)

Submission status: Runtime Error

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

E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)
#print(E)

def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1
#print(visited)

G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)
#print(G)

ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(int,input().split()))
    p = [p[k]-1 for k in range(N)]
    parent = [k for k in range(N)]

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

    def unite(x,y):
        if find(x) != find(y):
            parent[find(x)] = find(y)

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

    ans = 0
    for k in range(N):
        if find(k) == find(p[k]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

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

Submission status: Runtime Error

Solution code:
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True


a,b=map(int,input().split())
*p,=map(int,input().split())
u=UNION_FIND(a)
d=defaultdict(list)

p=array(p)
for i in range(b):
    x,y=map(int,input().split())
    u.union(x-1,y-1)
for i in range(a):
    ans+=(u.root(i)==u.root(p[i]))
print(ans)

Submission status: Runtime Error

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)