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:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
uf = {}

def dfs(cld):
    if cld not in uf:
        return []
    elif uf[cld] < 0:
        return [cld]
    return dfs(uf[cld]) + [cld]

for xy in xys:
    xin = (xy[0] in uf)
    yin = (xy[1] in uf)
    xp = dfs(xy[0])
    yp = dfs(xy[1])
    if xin and yin:
        if uf[xp[0]] == uf[yp[0]]:
            uf[xy[1]] = xp[0]
            uf[xp[0]] -= 1
        elif uf[xp[0]] < uf[yp[0]]:
            uf[xy[1]] = xp[0]
        else:
            uf[xy[0]] = yp[0]
    elif xin:
        uf[xy[1]] = xp[0]
    elif yin:
        uf[xy[0]] = yp[0]
    else:
        uf[xy[0]] = -1
        uf[xy[1]] = xy[0]
count = 0
for i in range(n):
    num = i + 1
    pi = p[i]
    if num == pi or sum(set(dfs(num)) & set(dfs(pi))) > 0:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
uf = {}

def dfs(cld):
    if cld not in uf:
        return []
    elif uf[cld] == None:
        return [cld]
    return dfs(uf[cld]) + [cld]

for xy in xys:
    xin = (xy[0] in uf)
    yin = (xy[1] in uf)
    xp = dfs(xy[0])
    yp = dfs(xy[1])
    if xin and yin:
        if len(xp) > len(yp):
            uf[xy[1]] = xp[0]
        else:
            uf[xy[0]] = yp[0]
    elif xin:
        uf[xy[1]] = xp[0]
    elif yin:
        uf[xy[0]] = yp[0]
    else:
        uf[xy[0]] = None
        uf[xy[1]] = xy[0]
count = 0
for i in range(n):
    num = i + 1
    pi = p[i]
    if sum(set(dfs(num)) & set(dfs(pi))) > 0:
        count += 1
    elif num == pi:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
uf = {}

def dfs(cld):
    if cld not in uf:
        return []
    elif uf[cld] == None:
        return [cld]
    elif cld in uf:
        return dfs(uf[cld]) + [cld]

for xy in xys:
    xin = (xy[0] in uf)
    yin = (xy[1] in uf)
    xp = dfs(xy[0])
    yp = dfs(xy[1])
    if xin and yin:
        if len(xp) > len(yp):
            uf[xy[1]] = xy[0]
        else:
            uf[xy[0]] = xy[1]
    elif xin:
        uf[xy[1]] = xp[0]
    elif yin:
        uf[xy[0]] = yp[0]
    else:
        uf[xy[0]] = None
        uf[xy[1]] = xy[0]
count = 0
for i in range(n):
    num = i + 1
    pi = p[i]
    if sum(set(dfs(num)) & set(dfs(pi))) > 0:
        count += 1
    elif num == pi:
        count += 1
print(count)

Submission status: Runtime Error

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

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]

for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        
    else:
        par[y]=root(x)

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

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''

Submission status: Runtime Error

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

cat=[0]*(n+1)
cnt=0

for i in range(m):
    x, y=map(int, input().split())
    if cat[x]==0 and cat[y]==0:
        # new set
        cnt=cnt+1
        cat[x]=cnt
        cat[y]=cnt
    else:
        cat[x], cat[y]=cat[x]+cat[y], cat[x]+cat[y]

        
        dp.append(set())
        dp[cat[x]].add(x)
        dp[cat[x]].add(y)
        print('i,cat[x],cat[y],cat,dp=',i,cat[x],cat[y],cat,dp)
        

dp=[set()]*cnt
p_set=[set()]*cnt

for i in range(n+1):
    if cat[i]==0:
    else:
        dp[cat[i]].add[i]
        p_set[cat[i]].add[p[i]]

ans=0
for i in range(cnt+1):
    ans=ans+len(dp[i]&p_set[i])

print(ans)

Submission status: Runtime Error

Solution code:
def Root(x):
  if L[x] == x:
    return x
  else:
    return Root(L[x])

N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
L = [i for i in range(N + 1)]
for i in range(M):
  t = list(map(int, input().split()))
  L[Root(min(t))] = L[Root(max(t))]

Ans = 0
for i in range(N):
  if Root(i + 1) == Root(p[i]):
    Ans += 1
print(Ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))
t = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(m)]

a = [set() for _ in range(n)]
for i, j in t:
    a[p[i]].add(p[j])
    a[p[j]].add(p[i])

def dfs(x, v):
    if v[x] == 0:
        v[x] = 1
        for i in a[x]:
            dfs(i, v)

mx = []
for i in range(n):
    v = [0]*n
    dfs(i, v)
    mx.append(v)

ans = 0
for i in range(n):
    tmp = p[i]
    idx = p.index(i)
    if mx[tmp][i]:
        ans += 1
        p[i] = i
        p[idx] = tmp
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
from pprint import pprint
import numpy as np
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

# graph = [[0 for _ in range(N)] for _ in range(N)]
graph = np.zeros((N,N), dtype=bool)
# visited = [0 for _ in range(N)]
visited = np.zeros((N, ), dtype=bool)

for x,y in xy:
    graph[x-1,y-1] = True
    graph[y-1,x-1] = True

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = True
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   #深さ優先探索
        # i = que.popleft() #幅優先探索
        for n in range(N):
            if graph[i,n] == True and visited[n] == False:
                visited[n] = True
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == False:
        grps.append(dfs(i))

ans = 0
for g_list in grps:

    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)

Submission status: Runtime Error

Solution code:
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        
        
      
        
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
class Union_find:
    def __init__(self,n):
        self.group=[i for i in range(n)]
    
    def root(self,x):
        if(self.group[x]==x):
            return x
        else:
            tmp=self.root(self.group[x])
            self.group[x]=tmp
            return tmp
    
    def make(self,x,y):
        self.group[self.root(x)]=y
    
    def judge(self,x,y):
        if(self.root(x)==self.root(y)):
            return True
        else:
            return False


n,m=map(int,input().split())
T=Union_find(n+1)
P=list(map(int,input().split()))

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


ans=0

for i in range(n):
    if(T.judge(P[i],i+1)):
        ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    stack = deque(paths[i]) if i in paths.keys() else []
    cluster = set([i]+paths[i])
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in cluster:
                stack.append(k)
                cluster.add(k)
    path_id += 1
# print(connected)

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split(" "))
p = list(map(int,input().split(" ")))
xy = []
for i in range(M):
    aa = input().split(" ")
    x = int(aa[0])
    y = int(aa[1])
    xy.append([x,y])
link = []
linklist = []
for i in range(M):
    x = xy[i][0]
    y = xy[i][1]
    if (x not in linklist)and(y not in linklist):
        #一度も出現していないので新たなに枝を作成
        linklist.append(x)
        linklist.append(y)
        link.append(xy[i])
    elif (x in linklist)and(y in linklist):
        #枝と枝を結ぶ
        for j in range(len(link)):
            if x in link[j]:
                Xnode = link[j]
                break
        for j in range(len(link)):
            if y in link[j]:
                Ynode = link[j]
                break
        new = Xnode+Ynode
        link.append(new)
        link.remove(Xnode)
        link.remove(Ynode)
    else:
        #枝を広げる
        for j in range(len(link)):
            if x in link[j]:
                link[j].append(y)
                break
            if y in link[j]:
                link[j].append(x)
                break
count = 0
for i in range(len(p)):
    if p[i] == (i+1):
        count += 1
    else:
        for j in range(len(link)):
            if (p[i] in link[j])and((i+1) in link[j]):
                count += 1
print(count)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
P=list(map(int,input().split()))
X=[]
for i in range(m):
    X.append(list(map(int,input().split())))



import networkx as nx

G = nx.Graph()

for i in range(n):
    G.add_node(i+1)
    
#print(G.nodes())

for i in range(m):
    G.add_edge(X[i][0],X[i][1])
    G[X[i][0]][X[i][1]]["capacity"] = 1.0

#print(G.edges())

#print(nx.maximum_flow(G, 1, 2)[0])



#print(G.successors(1))

co=0
for i in range(n):
    #print(nx.maximum_flow(G, i+1, P[i])[0])
    if i+1==P[i] or nx.maximum_flow(G, i+1, P[i])[0]==1.0:
        co+=1
    #elif nx.maximum_flow(G, i+1, P[i])[0]==1.0 :
    #    co+=1
print(co)

Submission status: Runtime Error

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:-1 for i in range(n)}
def U(x):
  if D[x]<0:
    D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I()
  if D[U(x-1)]>D[U(y-1)]:
  	D[U(x-1)]=U(y-1)
  elif D[U(x-1)]<D[U(y-1)]:
    D[U(y-1)]=U(x-1)
  else:
    D[U(x-1)]-=1
    D[U(y-1)]=U(x-1)
print(sum(U(i)==U(p-1)for i,p in enumerate(P)))

Submission status: Runtime Error

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n)}
def U(x):
  if D[x]!=x:
    D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x)]=U(y)
print(sum(U(i-1)==U(p)for i,p in enumerate(P)))

Submission status: Runtime Error

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n)}
def U(x):
  if D[x]!=x:
    D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x)]=U(y)
print(sum(U(i)==U(p)for i,p in enumerate(P)))

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:

			if self.tree[xr]==self.tree[yr]:
				self.tree[xr]-=1
				self.tree[yr]=xr
			else:
			    if self.tree[xr]>self.tree[yr]:
					self.tree[xr]=yr
				else:
					self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
       		self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self, x):
        if self.tree[x] < 0:
            return x
        else:
            #self.tree[x] = self.find(self.id[x])
            return self.find(self.id[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self, x):
        if self.tree[x] < 0:
            return x
        else:
            self.tree[x] = self.find(self.id[x])
            return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self, x):
        if self.tree[x] < 0:
            return x
        else:
            self.tree[x] = self.find(self.id[x])
            return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
            self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Runtime Error

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n+1)}
def U(x):
  if D[x]!=x:D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x, y= I():D[U(x)]=U(y)
print(sum(U(i)==U(p)for i,p in enumerate(P,1)))

Submission status: Runtime Error

Solution code:
class UnionFind:
	def __init__(self,node):
		self.par=[x for x in range(node)]
		self.rank=[1]*(node)
	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):
		rx=self.find(x)
		ry=self.find(y)
		if rx==ry:
			return False
		else:
			if self.rank[rx]<self.rank[ry]:
				self.par[rx]==ry
			else:
				self.par[ry]==rx
				if self.rank[rx]==self.rank[ry]:
					self.rank[rx]+=1
		return True
def main(self):
	n,q=map(int,input().split())
	li=[]
	sol=self.UnionFind(n)
	for _ in [0]*q:
		j,a,b=map(int input().split())
		if t==0:
			sol.unite(a,b)
		else:
			li.append("Yes" if sol.find(a)==sol.find(b) else "No")
	return "\n".join(li)
print(main())

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> setSize;

    UnionFind(unsigned int size) {
        parent.resize(size + 1);
        iota(parent.begin(), parent.end(), 0);
        setSize.resize(size + 1, 1);
    }

    // xとyが同じ集合に属するか
    bool isSameSet(int x, int y) {
        return findRoot(x) == findRoot(y);
    }

    // xとyの属する集合を併合
    void unionSet(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y) { return; }

        parent[x] = y;
        setSize[y] += setSize[x];
    }

private:
    // 木の根を求める
    int findRoot(int x) {
        if (parent[x] == x) {
            return x;
        }
        else {
            return parent[x] = findRoot(parent[x]);
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    vector<int> num_idx(N);
    FOR(i, 0, N) {
        cin >> P[i];
        P[i]--;
        num_idx[P[i]] = i;
    }

    UnionFind uf(N);
    FOR(i, 0, M) {
        int x, y;
        cin >> x >> y;
        uf.unionSet(x - 1, y - 1);
    }


    int ans = 0;
    FOR(i, 0, N) {
        if (P[i] == i) {
            ans++;
        }
        else {
            int idx = num_idx[i];
            ans += uf.isSameSet(i, idx);
        }
    }
    print(ans);

    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

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

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

swp = []
for m in range(M):
    x, y = map(int, input().split())
    swp.append((x, y))
    
# print(swp)

G_d = np.zeros((N, N), dtype=int)

for s in swp:
    G_d[s[0]-1][s[1]-1] = 1
    G_d[s[1]-1][s[0]-1] = 1

# print(G_d)

G_s = csr_matrix(G_d)

cc_sizes, ccs = connected_components(G_s, directed=False)


# print(cc_sizes)
# print("##")
# print(ccs)

total = 0
for i in range(N):
    pi_pos = P.index(i+1)
    if ccs[pi_pos] == ccs[i]:
        total += 1

print(total)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
	buf = input().split()
	N = int(buf[0])
	M = int(buf[1])
	
	buf = input().split()
	p = np.zeros(N)
	for i in range(N):
		p[i] = int(buf[i])-1
	
	g = []
	ing = set()
	
	for i in range(M):
		buf = input().split()
		x = int(buf[0])-1
		y = int(buf[1])-1
		if(not(x in ing) and not(y in ing)):
			g.append(set([x, y]))
		elif((x in ing) and not(y in ing)):
			for j in range(len(g)):
				if(x in g[j]):
					g[j].add(y)
		elif(not(x in ing) and (y in ing)):
			for j in range(len(g)):
				if(y in g[j]):
					g[j].add(x)
		else:
			a, b = 0, 0
			for j in range(len(g)):
				if(x in g[j]):
					a = j
				if(y in g[j]):
					b = j
			g[a] = g[a] | g[b]
			g.pop(b)
		ing.add(x)
		ing.add(y)
	#print(g)
	#print(ing)
	r = 0
	gc = []
	for i in range(len(g)):
		tag = list(g[i])
		buf = [int(p[tag[j]]) for j in range(len(tag))]
		r += len(set(tag) & set(buf))
		#print(tag)
		#print(buf)
	mihon = set(np.arange(N))
	dontmove = mihon - ing
	#print(dontmove)
	#print(len(dontmove))
	for index in dontmove:
		#print(index)
		if(index == p[index]):
			r += 1
	print(r)
			
main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
	buf = input().split()
	N = int(buf[0])
	M = int(buf[1])
	
	buf = input().split()
	p = np.zeros(N)
	for i in range(N):
		p[i] = int(buf[i])-1
	
	xy = []
	for i in range(M):
		buf = input().split()
		x = int(buf[0])-1
		y = int(buf[1])-1
		xy.append([x, y])

	g = []
	ing = set()
	
	for i in range(M):
		#print(xy[i])
		#print(g)
		x = xy[i][0]
		y = xy[i][1]
		if(not(x in ing) and not(y in ing)):
			g.append(set(xy[i]))
		elif((x in ing) and not(y in ing)):
			for j in range(len(g)):
				if(x in g[j]):
					g[j].add(y)
		elif(not(x in ing) and (y in ing)):
			for j in range(len(g)):
				if(y in g[j]):
					g[j].add(x)
		else:
			a, b = 0, 0
			for j in range(len(g)):
				if(x in g[j]):
					a = j
				if(y in g[j]):
					b = j
			g[a] = g[a] | g[b]
			g.pop(b)
		ing.add(x)
		ing.add(y)
	#print(g)
	#print(ing)
	r = 0
	gc = []
	for i in range(len(g)):
		tag = list(g[i])
		buf = [int(p[tag[j]]) for j in range(len(tag))]
		r += len(set(tag) & set(buf))
		#print(tag)
		#print(buf)
	mihon = set(np.arange(N))
	dontmove = mihon - ing
	#print(dontmove)
	#print(len(dontmove))
	for index in dontmove:
		#print(index)
		if(index == p[index]):
			r += 1
	print(r)
			
main()

Submission status: Runtime Error

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

def m():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    color = [-1] * (n+1)

    def dfs(v, c):
        s = []
        s.append(v)
        color[v] = c
        while len(s) != 0:
            a = s.pop()
            for elem in g[a]:
                if color[elem] == -1:
                    dfs(elem, c)

    k = 0
    for i in range(1, n):
        if color[i] == -1:
            dfs(i,k)
            k +=1
    ans = 0
    for i in range(n):
        if color[p[i]] == color[i+1]:
            ans +=1
    return ans

print(m())

Submission status: Runtime Error

Solution code:

n,m = [int(x) for x in input().split()]
#n,m = int(input().split())

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])
    


def search(n,o,g,depth,depthM,visited):
    l = d.get(n,[])
    # print("depth")
    # print(depth)
    if n == g:
        return True
    if l==[]:
        return False
    for nn in l:
        if nn in visited:
            continue
        else:
            visited.add(nn)
        if nn == g:
            #print("true")
            return True
        
        elif nn == o:
            continue
        elif depth>depthM:
            return False
        else:
            if search(nn,o,g,depth+1,depthM,visited):
                #print("True")
                return True
    return False

count=0   
for i, n in enumerate(a):
    visited = set()
    if search(n,n,i+1,0,m,visited):
        count+=1
print(count)

Submission status: Runtime Error

Solution code:

n,m = [int(x) for x in input().split()]
#n,m = int(input().split())

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])
    

def search(n,o,g,depth,depthM):
    l = d.get(n,[])
    # print("depth")
    # print(depth)
    if n == g:
        return True
    if l==[]:
        return False
    for nn in l:
        if nn == g:
            #print("true")
            return True
        elif nn == o:
            continue
        elif depth>depthM:
            return False
        else:
            if search(nn,o,g,depth+1,depthM):
                #print("True")
                return True
    return False

count=0   
for i, n in enumerate(a):
    if search(n,n,i+1,0,m):
        count+=1
print(count)

Submission status: Runtime Error

Solution code:

n,m = [int(x) for x in input().split()]
#n,m = int(input().split())

a = [int(x) for x in input().split()]

d = {}
for _ in range(m):
    x = input()
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])
    

def search(n,o,g,depth,depthM):
    l = d.get(n,[])
    # print("depth")
    # print(depth)
    if n == g:
        return True
    if l==[]:
        return False
    for nn in l:
        if nn == g:
            #print("true")
            return True
        elif nn == o:
            continue
        elif depth>depthM:
            return False
        else:
            if search(nn,o,g,depth+1,depthM):
                #print("True")
                return True

count=0   
for i, n in enumerate(a):
    if search(n,n,i+1,0,m):
        count+=1
print(count)

Submission status: Runtime Error

Solution code:

n,m = [int(x) for x in input().split()]
#n,m = int(input().split())

a = [int(x) for x in input().split()]

d = {}
x = input()
while x!="":
    t = [int(x) for x in x.split()]
    d.setdefault(t[0],[])
    d[t[0]].append(t[1])
    d.setdefault(t[1],[])
    d[t[1]].append(t[0])
    x = input()

def search(n,o,g,depth,depthM):
    l = d.get(n,[])
    # print("depth")
    # print(depth)
    if n == g:
        return True
    if l==[]:
        return False
    for nn in l:
        if nn == g:
            #print("true")
            return True
        elif nn == o:
            continue
        elif depth>depthM:
            return False
        else:
            if search(nn,o,g,depth+1,depthM):
                #print("True")
                return True

count=0   
for i, n in enumerate(a):
    if search(n,n,i+1,0,m):
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
def saiki(a):
  c = l[a]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = i
    saiki(z)
#Union find
y = [0] * n
for i in range(0,n):
  if y[i] == 0:
    y[i] = i
  saiki(i)
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
import copy
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
def dfs(x,y):
  f = c[x]
  while len(f) > 0:
    z = f.pop()
    if z  == y:
      return True
    if dfs(z,y) == True:
      return True
for i in range(n):
  if x[i] == i+1:
    ans +=1
  else:
    c = copy.deepcopy(l)
    if dfs(x[i],i+1) == True:
      ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]
 
avl=defaultdict(list)
for pi in pair:
    avl[pi[0]].append(pi[1])
    avl[pi[1]].append(pi[0])
 
def trv(src, dst, alr=[]):
    ans=False
    if src==dst or dst in avl[src]:
        return True
    for a in avl[src]:
        if a not in alr:
            alr.append(a)            
            ans|=trv(a, dst, alr)
    return ans
 
cnt=0
for i,pi in enumerate(p):
    if trv(pi, i, []):
        cnt+=1
print(cnt)