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: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
rem = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    rem[x] = False
    rem[y] = False
count = 0
for i in range(N):
    if rem[i] and p[i] == i:
        count += 1
alr = [i for i in rem]
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = [p.index(i)]
        numlist = [i]
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.append(num)
            indlist.append(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        for num in numlist:
            if num in indlist:
                count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
rem = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    rem[x] = False
    rem[y] = False
count = 0
for i in range(N):
    if rem[i] and p[i] == i:
        count += 1
alr = rem.copy()
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = [p.index(i)]
        numlist = [i]
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.append(num)
            indlist.append(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        for num in numlist:
            if num in indlist:
                count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
rem = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    rem[x] = False
    rem[y] = False
count = 0
for i in range(N):
    if rem[i] and p[i] == i:
        count += 1
alr = rem.copy()
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = [j[1] for j in xy[i]]
        numlist = [j[0] for j in xy[i]]
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.append(num)
            indlist.append(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        for num in numlist:
            if num in indlist:
                count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
rem = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    rem[x] = False
    rem[y] = False
count = 0
for i in range(N):
    if rem[i] and p[i] == i:
        count += 1
alr = rem.copy()
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = [j[0] for j in xy[i]]
        numlist = [j[1] for j in xy[i]]
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.append(num)
            indlist.append(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        for num in numlist:
            if num in indlist:
                count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N):
  p[i]-=1

# UnionFindして、同じグループに同じ添え字と番号のペアが存在してれば1

parent=[i for i in range(N)]
depth=[0 for i in range(N)]
def root(x):
  if parent[x]!=x:
    x=parent[x]
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots={}
ans=0
for i in range(N):
  r=root(i)
  if r not in roots:
    roots[r]=set()
  if i in roots[r]:
    ans+=1
  else:
    roots[r].add(i)
  if p[i] in roots[r]:
    ans+=1
  else:
    roots[r].add(p[i])

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N):
  p[i]-=1

# UnionFindして、同じグループに同じ添え字と番号のペアが存在してれば1

parent=[i for i in range(N)]
depth=[0 for i in range(N)]
def root(x):
  if parent[x]!=x:
    x=parent[x]
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i])
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
print(ans)

Submission status: Wrong Answer

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

# UnionFindして、同じグループに同じ添え字と番号のペアが存在してれば1

parent=[i for i in range(N)]
depth=[0 for i in range(N)]
def root(x):
  if parent[x]!=x:
    x=parent[x]
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]-1]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i]-1)
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
print(ans)

Submission status: Wrong Answer

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

# UnionFindして、同じグループに同じ添え字と番号のペアが存在してれば1

parent=[i for i in range(N)]
depth=[0 for i in range(N)]
def root(x):
  temp=x
  if parent[x]!=x:
    x=parent[x]
  parent[temp]=x
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]-1]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i]-1)
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
print(ans)

Submission status: Wrong Answer

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

parent=[i for i in range(N)]
depth=[0 for i in range(N)]

def root(x):
  temp=x
  if parent[x]!=x:
    x=parent[x]
  parent[temp]=x
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]-1]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i]-1)
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  if len(roots_nums[k])<2:
    continue
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
  
for item in roots_inds.items():
  if len(item[1])==1 and parent[item[0]]==item[0]:
    ans+=1

print(ans)

Submission status: Wrong Answer

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

parent=[i for i in range(N)]
depth=[0 for i in range(N)]

def root(x):
  temp=x
  if parent[x]!=x:
    x=parent[x]
  parent[temp]=x
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]-1]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i]-1)
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
  
rest=set([i for i in range(N)])
rest=rest-set(roots_nums)
rest=rest-set(roots_inds)
for re in rest:
  if parent[re]==re:
    ans+=1

print(ans)

Submission status: Wrong Answer

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

parent=[i for i in range(N)]
depth=[0 for i in range(N)]
def root(x):
  temp=x
  if parent[x]!=x:
    x=parent[x]
  parent[temp]=x
  return parent[x]

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

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
  
for i in range(M):
  x,y=map(int,input().split())
  union(x-1,y-1)

roots_nums={}
roots_inds={}
for i in range(N):
  r=root(i)
  if r not in roots_nums:
    roots_nums[r]=[p[i]-1]
    roots_inds[r]=[i]
  else:
    roots_nums[r].append(p[i]-1)
    roots_inds[r].append(i)
    
ans=0
for k in roots_nums.keys():
  ans+=len(set(roots_nums[k])&set(roots_inds[k]))
  
print(ans)

Submission status: Wrong Answer

Solution code:
print("reference: maspy")

import sys
input = sys.stdin.readline
 
N,M = map(int,input().split())
 
p = [0] + [int(x) for x in input().split()]
root = list(range(N + 1))
print("root:", root)
depth = [0]*(N+1) # 深さを定義する必要がある。
 
# 連結成分を作る
def find_root(x):
  y = root[x]
  if x == y:
    return y
  z = find_root(y)
  root[x] = z # やはりここの更新が必要。
  return z
 
def merge(x,y): # union-findの核心part2。
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return
  if depth[rx] > depth[ry]: # 深い方を根にする。
    root[ry] = rx
  elif depth[ry] > depth[rx]:
    root[rx] = ry
  else: # バランスを取る。こういうアルゴリズムと覚える。
    root[rx] = ry
    depth[rx] += 1
    
XY = [[int(x) for x in input().split()] for _ in range(M)]
for x,y in XY:
  merge(x,y)

# 連結成分内は自由に作れる
# p[i]とiが同じ連結成分にあると1点
answer = 0
for i, x in enumerate(p[1:], 1): # enumerateの第二変数はstartで1ずらせる。
  print(i, x)
  if find_root(i) == find_root(x):
    answer += 1

print(answer)

Submission status: Wrong Answer

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

k=[0]*n
l=0
for i in range(m):
    x,y=xy[i][0],xy[i][1]
    if k[x-1]==0 and k[y-1]==0:
        l+=1
        k[x-1]=l
        k[y-1]=l
    elif k[x-1]==0:
        k[x-1]=k[y-1]
    elif k[y-1]==0:
        k[y-1]=k[x-1]
    else:
        if k[x-1]<k[y-1]:
            a,b=k[x-1],k[y-1]
        elif k[y-1]<k[x-1]:
            a,b=k[y-1],k[x-1]
        for i in range(n):
            if k[i]==b:
                k[i]=a

t1=[[] for i in range(l)]
t2=[[] for i in range(l)]
for i in range(n):
    if k[i]!=0:
        t1[k[i]-1].append(i+1)
        t2[k[i]-1].append(p[i])

co=0
for i in range(l):
    co+=len(set(t1[i]) & set(t2[i]))

print(co)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[int(i) for i in input().split()]
xy=[]

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


xy=sorted(xy,key=lambda x:(x[0],x[1]))
#print(xy)
k=[0]*n
l=0
for i in range(m):
    x,y=xy[i][0],xy[i][1]
    if k[x-1]==0 and k[y-1]==0:
        l+=1
        k[x-1]=l
        k[y-1]=l
    elif k[x-1]==0:
        k[x-1]=k[y-1]
    elif k[y-1]==0:
        k[y-1]=k[x-1]
    else:
        if k[x-1]<k[y-1]:
            a,b=k[x-1],k[y-1]
            for i in range(n):
                if k[i]==b:
                    k[i]=a
        elif k[y-1]<k[x-1]:
            a,b=k[y-1],k[x-1]
            for i in range(n):
                if k[i]==b:
                    k[i]=a

#print(k)

t1=[[] for i in range(l)]
t2=[[] for i in range(l)]
for i in range(n):
    #print(k[i])
    if k[i]!=0:
        t1[k[i]-1].append(i+1)
        t2[k[i]-1].append(p[i])
#print(t1)
#print(t2)

co=0
for i in range(l):
    co+=len(set(t1[i]) & set(t2[i]))

print(co)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[int(i) for i in input().split()]
xy=[]

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


xy=sorted(xy,key=lambda x:(x[0],x[1]))
print(xy)
k=[0]*n
l=0
for i in range(m):
    x,y=xy[i][0],xy[i][1]
    if k[x-1]==0 and k[y-1]==0:
        l+=1
        k[x-1]=l
        k[y-1]=l
    elif k[x-1]==0:
        k[x-1]=k[y-1]
    elif k[y-1]==0:
        k[y-1]=k[x-1]
    else:
        if k[x-1]<k[y-1]:
            a,b=k[x-1],k[y-1]
            for i in range(n):
                if k[i]==b:
                    k[i]=a
        elif k[y-1]<k[x-1]:
            a,b=k[y-1],k[x-1]
            for i in range(n):
                if k[i]==b:
                    k[i]=a
            
print(k)

t1=[[] for i in range(l)]
t2=[[] for i in range(l)]
for i in range(n):
    #print(k[i])
    if k[i]!=0:
        t1[k[i]-1].append(i+1)
        t2[k[i]-1].append(p[i])
print(t1)
print(t2)

co=0
for i in range(l):
    co+=len(set(t1[i]) & set(t2[i]))

print(co)

Submission status: Wrong Answer

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 '\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):
    a, b = map(int,input().split())
    uf.union(a-1,b-1)
A = list(uf.all_group_members().values())
a = len(A)
B =[[] for i in range(a)]
import bisect
ans = 0
for i in range(a):
    S = A[i]
    for j in range(len(S)):
        s = S[j]
        insert_index = bisect.bisect_left(B[i],P[s]-1)
        B[i].insert(insert_index,P[s]-1)
    p = 0
    
    for k in range(len(S)):
        if p == 0:
            x = B[i].pop(0)
            p = 1
        if x == S[k]:
            p = 0
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ad=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  uf.merge(b-1,a-1)
print(sum(1 for i in range(n) if uf.parent[i]==uf.parent[ad[i]-1]))

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
n,m=map(int,input().split())
ad=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  uf.merge(b-1,a-1)
print(sum(1 for i in range(n) if uf.parent[i]==uf.parent[ad[i]-1]))

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
n,m=map(int,input().split())
ad=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:a,b=b,a
  uf.merge(a-1,b-1)
print(sum(1 for i in range(n) if uf.parent[i]==uf.parent[ad[i]-1]))

Submission status: Wrong Answer

Solution code:
# D - Equals

import numpy as np
import sys, bisect
from collections import deque

N, M = map(int, sys.stdin.buffer.readline().split())
p = np.array(list(map(int, sys.stdin.buffer.readline().split()))) - 1
xy = np.array(sys.stdin.buffer.read().split(), np.int64) - 1

x = xy[::2]
y = xy[1::2]

neighbor = [[] for _ in range(N)]
for idx in range(M):
    neighbor[x[idx]].append(y[idx])
    neighbor[y[idx]].append(x[idx])
    
    
print("test")
    
# can_swap = []
# visited = [-1]*N

# for start in range(N):
#     if visited[start] == -1:
#         tmp = [start] # startから到達可能なpointのリスト
#         visited[start] = 1
#         d = deque([start])
#         while d:
#             current_point = d.pop()
#             visited[current_point] = 1
#             for next_point in neighbor[current_point]:
#                 if visited[next_point] == -1:
#                     d.append(next_point)
#                     tmp.append(next_point)
#         can_swap.append(tmp)                

# ans = 0
# for idx_group in can_swap:
#     tmp_p = [p[idx] for idx in idx_group]
#     ans += len(set(tmp_p) & set(idx_group))

# print(ans)

Submission status: Wrong Answer

Solution code:
# D - Equals

import numpy as np
import sys, bisect
from collections import deque

N, M = map(int, sys.stdin.buffer.readline().split())
p = np.array(list(map(int, sys.stdin.buffer.readline().split()))) - 1
xy = np.array(sys.stdin.buffer.read().split(), np.int64) - 1

x = xy[::2]
y = xy[1::2]

neighbor = [[] for _ in range(N)]
for idx in range(M):
    neighbor[x[idx]].append(y[idx])
    neighbor[y[idx]].append(x[idx])
    
can_swap = []
visited = [-1]*N

for start in range(N):
    if visited[start] == -1:
        tmp = [start] # startから到達可能なpointのリスト
        visited[start] = 1
        d = deque([start])
        while d:
            current_point = d.pop()
            visited[current_point] = 1
            for next_point in neighbor[current_point]:
                if visited[next_point] == -1:
                    d.append(next_point)
                    tmp.append(next_point)
        can_swap.append(tmp)                

print("test")
# ans = 0
# for idx_group in can_swap:
#     tmp_p = [p[idx] for idx in idx_group]
#     ans += len(set(tmp_p) & set(idx_group))

# print(ans)

Submission status: Wrong Answer

Solution code:
# D - Equals

import numpy as np
import sys, bisect
from collections import deque

N, M = map(int, sys.stdin.buffer.readline().split())
p = np.array(list(map(int, sys.stdin.buffer.readline().split()))) - 1
xy = np.array(sys.stdin.buffer.read().split(), np.int64) - 1

x = xy[::2]
y = xy[1::2]

neighbor = [[] for _ in range(N)]
for idx in range(M):
    neighbor[x[idx]].append(y[idx])
    neighbor[y[idx]].append(x[idx])
    
can_swap = []
visited = [-1]*N

for start in range(N):
    if visited[start] == -1:
        tmp = [start] # startから到達可能なpointのリスト
        visited[start] = 1
        d = deque([start])
        while d:
            current_point = d.pop()
            visited[current_point] = 1
            for next_point in neighbor[current_point]:
                if visited[next_point] == -1:
                    d.append(next_point)
                    tmp.append(next_point)
        can_swap.append(tmp)                

ans = 0
for idx_group in can_swap:
    tmp_p = []
    for idx in idx_group:
        tmp_p.append(p[idx])
    tmp_p.sort()
    for idx in idx_group:
        try:
            if tmp_p[bisect.bisect_left(tmp_p, idx)] == idx:
                ans += 1
        except IndexError:
            pass

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
P = list(map(int,input().split()))
R = [list(map(int,input().split())) for i in range(m)]
for r in R:
  r.sort()
R.sort()
U = [-1]*n
for r in R:
    if U[r[0]-1]==-1:
        if U[r[1]-1]==-1:
            U[r[0]-1] = r[0]
            U[r[1]-1] = r[0]
        else:
            U[r[0]-1] = U[r[1]-1]
    else:
        if U[r[1]-1]==-1:
            U[r[1]-1] = U[r[0]-1]
        else:
            for i in range(n):
                if U[i] == U[r[1]-1]:
                    U[i] = U[r[0]-1]

test = []

count = 0
for i in range(n):
    if U[P[i]-1] == U[i] and U[i] != -1:
        count += 1
        test += [i+1]
    elif U[i] == -1 and P[i]-1 == i:
        count += 1
        test += [i+1]

print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
P = list(map(int,input().split()))
R = [list(map(int,input().split())) for i in range(m)]
for r in R:
  r.sort()
R.sort()
U = [-1]*n
for r in R:
    if U[r[0]-1]==-1:
        if U[r[1]-1]==-1:
            U[r[0]-1] = r[0]
            U[r[1]-1] = r[0]
        else:
            U[r[0]-1] = U[r[1]-1]
    else:
        if U[r[1]-1]==-1:
            U[r[1]-1] = U[r[0]-1]
        else:
            for i in range(n):
                if U[i] == U[r[1]-1]:
                    U[i] = U[r[0]-1]
count = 0
for i in range(n):
    if U[P[i]-1] == U[i] and U[i] != -1:
        count += 1
    elif U[i] == -1 and P[i]-1 == i:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = [0] + [int(x) for x in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:    return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:    self.rank[x] += 1

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

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = [0] + [int(x) for x in input().split()]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:    return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:    self.rank[x] += 1

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

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

unionUF, unionp, par = [], [], []
for i in range(1, N+1):
    temp = UF.par[i]
    if temp in par:
        unionUF[par.index(temp)].add(i)
        unionp[par.index(temp)].add(p[i])
    else:
        par.append(temp)
        unionUF.append(set([i]))
        unionp.append(set([p[i]]))

ans = 0
for i in range(len(unionUF)):
    ans += len(unionUF[i] & unionp[i])
print(ans)

Submission status: Wrong Answer

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


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

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

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

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

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

node_list = [UnionFindNode(i) for i in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    node_list[x-1].unite(node_list[y-1])

ans = 0
for i, p in enumerate(p_array):
    if node_list[i-1].find() == node_list[p-1].find() or i == p-1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v)-1 for v in input().split() ]
rank_list = [ 0 for i in range(n) ]
parent_list = [ i for i in range(n) ]


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

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]

    pa, pb = parent(a), parent(b)

    if pa != pb:
        if rank_list[pa] == rank_list[pb]:
            parent_list[b] = pa
            rank_list[pa] += 1
        elif rank_list[pa] > rank_list[pb]:
            parent_list[b] = pa
        elif rank_list[pb] > rank_list[pa]:
            parent_list[a] = pb

parent_list = [ parent(i) for i in parent_list ]
ans = 0
for i in range(n):
    if parent_list[num_list[i]] == parent_list[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

n, m = [ int(v) for v in input().split() ]
num_list = [ int(v)-1 for v in input().split() ]
rank_list = [ 0 for i in range(n) ]
parent_list = [ i for i in range(n) ]


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

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]

    pa, pb = parent_list[a], parent_list[b]

    if pa != pb:
        if rank_list[pa] == rank_list[pb]:
            parent_list[b] = pa
            rank_list[pa] += 1
        elif rank_list[pa] > rank_list[pb]:
            parent_list[b] = pa
        elif rank_list[pb] > rank_list[pa]:
            parent_list[a] = pb

parent_list = [ parent(i) for i in parent_list ]
ans = 0
for i in range(n):
    if parent_list[num_list[i]] == parent_list[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v)-1 for v in input().split() ]
rank_list = [ 0 for i in range(n) ]
parent_list = [ i for i in range(n) ]


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

for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]

    pa, pb = parent_list[a], parent_list[b]

    if pa != pb:
        if rank_list[pa] == rank_list[pb]:
            parent_list[b] = pa
            rank_list[pa] += 1
        elif rank_list[pa] > rank_list[pb]:
            parent_list[b] = pa
        elif rank_list[pb] > rank_list[pa]:
            parent_list[a] = pb


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