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 = [ 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(i) == parent(num_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 range(n) ]

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

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self, 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)

u = UnionFind(n)
for i in range(m):
    x = xy[i][0]
    y = xy[i][1]
    u.union(x, y)

idxs = []
for i in range(1, n+1):
    idxs.append(u.find(i))

idx_dict = dict()
for i in range(n):
    if idxs[i] not in idx_dict.keys():
        idx_dict[idxs[i]] = [i]
    else:
        idx_dict[idxs[i]].append(i)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
xy=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*M]
z=[[i,1] for i in range(N)]

def root_find(a):
    while(a!=z[a][0]):
        a=z[a][0]
    return a

def union(a,b):
    ra=root_find(a[0])
    rb=root_find(b[0])
    if z[ra][1]<=z[rb][1]:
        z[ra][0]=rb
        z[rb][1]=max(z[rb][1],z[ra][1]+1)
    else:
        z[rb][0]=ra
        z[ra][1]=max(z[ra][1],z[rb][1]+1)
    
for i in range(M):
    union(z[xy[i][0]],z[xy[i][1]])

for i in range(N):
    z[i][0]=root_find(z[i][0])

dic=dict()

for i in range(N):
    zz=z[i][0]
    if zz not in dic.keys():
        dic[zz]=[i]
    else:
        dic[zz].append(i)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
xy=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*M]
z=[[i,1] for i in range(N)]

def root_find(a):
    while(a!=z[a][0]):
        a=z[a][0]
    return a

def union(a,b):
    ra=root_find(a[0])
    rb=root_find(b[0])
    if z[ra][1]<=z[rb][1]:
        z[ra][0]=rb
        z[rb][1]=max(z[rb][1],z[ra][1]+1)
    else:
        z[rb][0]=ra
        z[ra][1]=max(z[ra][1],z[rb][1]+1)
    
for i in range(M):
    union(z[xy[i][0]],z[xy[i][1]])

for i in range(N):
    zz=z[i][0]
    zz=root_find(zz)

dic=dict()

for i in range(N):
    zz=z[i][0]
    if zz not in dic.keys():
        dic[zz]=[i]
    else:
        dic[zz].append(i)

list1=list(dic.values())
list2=[[] for _ in [0]*len(list1)]

for i in range(len(list1)):
    for a in list1[i]:
        list2[i].append(p[a])

cnt=0
for i in range(len(list1)):
    for a in list1[i]:
        if a in list2[i]:
            cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
line = input().split(" ")
n, m = int(line[0]), int(line[1])

line = input().split(" ")
operations = []
for i in range(m):
	test = input().split(" ")
	operations.append((int(test[0]),int(test[1])))

correct = []
line2 = []
for i in range(len(line)):
	line2.append(int(line[i]))
	correct.append(i+1)

count = 0
for l,c in zip(line2, correct):
	if l == c:
		count += 1

if count == n:
	print(count)
else:
	for i in range(len(operations)):
		if line2[operations[i][0]-1] == operations[i][1] or line2[operations[i][1]-1] == operations[i][0]:
			temp = line2[operations[i][0]-1] 
			line2[operations[i][0]-1] = line2[operations[i][1]-1]
			line2[operations[i][1]-1] = temp

count = 0
for l,c in zip(line2, correct):
	if l == c:
		count += 1

print(count)

Submission status: Wrong Answer

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

class UnionFindTree():
    def __init__(self, size):
        """
        Initializes `size` trees.
        size: size of union find tree
        """
        # initialize the map with n -> n
        self.__parent_map = range(size)

    def get_root(self, x):
        """
        Returns the root of tree which contains such given element.
        x: number of node
        """
        parent = self.__parent_map[x]
        if parent == x:
            return x
        else:
            root = self.get_root(parent)
            # shortens the finding path
            self.__parent_map[x] = root
            return root

    def unite(self, x, y):
        """
        combine two trees into one tree.
        """
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        # if x and y don't have the same root, combine then into one tree
        if root_x != root_y:
            self.__parent_map[x] = root_y

    def is_same(self, x, y):
        """
        Check the identity of given two tree.
        """
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        return root_x == root_y

    def get_raw_data(self):
        return self.__parent_map

def main():
    n, m = map(int, input().split())
    ps = map(lambda x: x-1, map(int, input().split()))
    tree = UnionFindTree(n)
    for _ in range(m):
        x, y = map(int, input().split())
        tree.unite(x - 1, y - 1)
    counter = 0
    for i in range(n):
        if tree.is_same(i, ps[i]):
            counter += 1
    print(counter)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Wrong Answer

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a
    #if (ue[b]==-1):
    #  dw[_a].append(b)
    #  ue[b]=_a
  #print (a,b)
#print (ue)
#print (dw)

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Wrong Answer

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a
    #if (ue[b]==-1):
    #  dw[_a].append(b)
    #  ue[b]=_a
  #print (a,b)
#print (ue)
#print (dw)
s = 0
for j in range(N):
  if (ue[j]==-1):
    le = len(dw[j])
    if (le==0):
      if pli[j]==j:
        s += 1
    else:
      x,y=0,0
      dw[j].append(j)
      dw[j].sort()
      xpli= [pli[it] for it in dw[j]]
      xpli.sort()
      len_dw = len(dw[j])
      len_xpli = len(xpli)
      for i in range(2*N):
        if (dw[j][x]==xpli[y]):
          s+=1
          x+=1
          y+=1
        elif (dw[j][x]<xpli[y]):
          x+=1
        else:
          y+=1
        if (x==len_dw or y==len_xpli):
            break
print (s)

Submission status: Wrong Answer

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a
    #if (ue[b]==-1):
    #  dw[_a].append(b)
    #  ue[b]=_a
  #print (a,b)
#print (ue)
#print (dw)
s = 0
for j in range(N):
  if (ue[j]==-1):
    le = len(dw[j])
    if (le==0):
      if pli[j]==j:
        s += 1
    else:
      x,y=0,0
      dw[j].append(j)
      dw[j].sort()
      xpli= [pli[it] for it in dw[j]]
      xpli.sort()
      len_dw = len(dw[j])
      len_xpli = len(xpli)
      #print (dw[j],xpli)
      for i in range(2*N):
        if (dw[j][x]==xpli[y]):
          s+=1
          x+=1
          y+=1
        elif (dw[j][x]<xpli[y]):
          x+=1
        else:
          y+=1
        if (x==len_dw or y==len_xpli):
            break
print (s)

Submission status: Wrong Answer

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a
    #if (ue[b]==-1):
    #  dw[_a].append(b)
    #  ue[b]=_a
  #print (a,b)
s = 0
for j in range(N):
  if (ue[j]==-1):
    le = len(dw[j])
    if (le==0):
      if pli[j]==j:
        s += 1
    else:
      x,y=0,0
      dw[j].append(j)
      dw[j].sort()
      pli.sort()
      len_dw = len(dw[j])
      len_pli = len(pli)
      for i in range(2*N):
        if (dw[j][x]==pli[y]):
          s+=1
          x+=1
          y+=1
        elif (dw[j][x]<pli[y]):
          x+=1
        else:
          y+=1
        if (x==len_dw or y==len_pli):
            break
print (s)

Submission status: Wrong Answer

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

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

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

    def unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[y] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

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

uni = Unionfind(N)
for i in range(M):
    x, y = map(int, input().split())
    uni.unite(x, y)

count = 0
for i in range(1, N+1):
    if uni.same(i, p[i-1]):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = (uf[x])
        return uf[x]

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

Submission status: Wrong Answer

Solution code:
def root(uf, x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf, uf[x])
        return uf[x]

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

def unite(uf, x, y):
    rx = root(uf, x)
    ry = root(uf, y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(uf, a, b)
for i in range(1, N+1):
    root(uf, i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
#for i in range(1, N+1):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1
print(str(ans))

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import operator


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(self, x, y):
        return self.find(x) == self.find(y)


a,b =  map(int, input().split())
l = list(map(int, input().split()))
uf = UnionFind(a)
for i in range(b):
    x,y =map(int, input().split())
    x-=1
    y-=1
    uf.union(x, y)  # (3)
ans=0
for i,t in enumerate(l):
    if uf.same(t-1,l[i]-1):ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x
    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
n, m = map(int, input().split())
p = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
place = Unionfind(n)
d = {}
for x, y in edges:
    place.union(x-1, y-1)
loot = [0] * n
for i in range(n):
    loot[i] = place.find(i)
    if loot[i] not in d:
        d[loot[i]] = {p[i]-1}
    else:
        d[loot[i]].add(p[i]-1)
counter = 0
for i in range(n):
    if i in d[loot[i]]:
        counter += 1
print(d)
print(counter)

Submission status: Wrong Answer

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

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 x==y:
            return
        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)
ans=0
for i,j in edges:
    uf.union(i,j)
for i in range(n):
    if uf.same_check(i,P[i]):
        ans+=1
print(ans)

Submission status: Wrong Answer

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_checker(x, y):
    return find(x) == find(y)

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

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)
S = {}
for i in range(N):
    S[p[i]] = par[i+1]
ans = 0
for i in range(N):
    if S[p[i]] == S[i+1]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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 []
    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 xp[0] == yp[0]:
            continue
        elif uf[xp[0]] == uf[yp[0]]:
            uf[yp[0]] = 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: Wrong Answer

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 xp[0] == yp[0]:
            continue
        elif uf[xp[0]] == uf[yp[0]]:
            uf[yp[0]] = 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: Wrong Answer

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

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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        
    else:
        if par[x]==0:
            par[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: Wrong Answer

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

par=[0]*(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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        
    else:
        if par[x]==0:
            par[x]=root(y)
        else:
            par[y]=root(x)

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]) or p[n]==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: Wrong Answer

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

par=[0]*(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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        
    else:
        if par[x]==0:
            par[x]=root(y)
        else:
            par[y]=root(x)

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]) or p[n]==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: Wrong Answer

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

par=[0]*(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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        #print('i,cnt=',i,cnt,'x,y,cat[x],cat[y],cat=',x,y,cat[x],cat[y],cat)
        
    else:
        if par[x]==0:
            par[x]=root(y)
        else:
            par[y]=root(x)

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

Submission status: Wrong Answer

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

par=[0]*(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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        #print('i,cnt=',i,cnt,'x,y,cat[x],cat[y],cat=',x,y,cat[x],cat[y],cat)
        
    else:
        if par[x]==0:
            par[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: Wrong Answer

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

par=[0]*(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 par[x]==0 and par[y]==0:
        # new set
        par[x]=x
        par[y]=x
        #print('i,cnt=',i,cnt,'x,y,cat[x],cat[y],cat=',x,y,cat[x],cat[y],cat)
        
    else:
        if par[x]==0:
            par[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)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

p_set = set(p)

grps = [set(xy[0])]
for x,y in xy[1:]:
    set_fg = False
    for g_set in grps:
        if x in g_set or y in g_set:
            g_set.add(x)
            g_set.add(y)
            set_fg = True

    if set_fg == False:
        grps.append({x, y})

print(0)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

p_set = set(p)

grps = [set(xy[0])]
for x,y in xy[1:]:
    set_fg = False
    for g_set in grps:
        if x in g_set or y in g_set:
            g_set.add(x)
            g_set.add(y)
            set_fg = True

    if set_fg == False:
        grps.append({x, y})

grps2 = [grps[0]]
for g_set in grps[1:]:
    set_fg = False
    for g_set2 in grps2:
        if len(g_set & g_set2) > 0:
            for f in list(g_set):
                g_set2.add(f)
            set_fg = True

    if set_fg == False:
        grps2.append(g_set)

# print(grps2)

ans = 0
tmpall = set([])
for g_set in grps2:
    tmpall = tmpall | g_set
    tmp = set([])
    for i in list(g_set):
        tmp.add(p[i-1])
    ans += len(g_set & tmp)

# 交換されない人
for i in list(p_set - tmpall):
    if p[i-1] == i:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

    if i not in paths.keys():
        pass
    else:
        stack = deque(paths[i])
        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: Wrong Answer

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
        if Xnode == Ynode:
            continue
        else:
            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: Wrong Answer

Solution code:
n,m = map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
par = [i for i in range(n)]
rank = [0]*n

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

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

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

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

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