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:
class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    # 親が同じか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True

Submission status: Wrong Answer

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

for _ in range(M):
    xy.append(list(map(int,input().split())))

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1

uf = UnionFind(N)
for x,y in xy:
    uf.unite(x-1,y-1)
count = 0
for i in p:
    if uf.is_same(i,p[i-1]):
        count += 1
print(count)

Submission status: Wrong Answer

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

save = [set()]
for i in range(m):
    x,y = list(map(int,input().split()))
    for z in save:
        if z == set():
            z.add(x)
            z.add(y)
            save.append(set())
            break
        else:
            if x in z or y in z:
                z.add(x)
                z.add(y)
                break

z1 = [set()]

for x in save:
    if x == set():
        break
    for y in range(len(z1)):
        if z1[y] == set():
            z1[y] = x
            z1.append(set())
            break
        else:
            if x & z1[y] != set():
                z1[y] = x | z1[y]
                break


res = 0

dic = {}

for x in z1:
    for y in x:
        dic[y] = x

for i in range(1,n+1):
    if i in dic:
        if i == p[i-1]:res += 1
        elif p[i-1] in dic[i]:res+=1
    elif i == p[i-1]:res += 1





print(res)

Submission status: Wrong Answer

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

save = [set()]
for i in range(m):
    x,y = list(map(int,input().split()))
    for z in save:
        if z == set():
            z.add(x)
            z.add(y)
            save.append(set())
            break
        else:
            if x in z or y in z:
                z.add(x)
                z.add(y)
                break

z1 = [set()]

for x in save:
    if x == set():
        break
    for y in range(len(z1)):
        if z1[y] == set():
            z1[y] = x
            z1.append(set())
            break
        else:
            if x & z1[y] != set():
                z1[y] = x | z1[y]
                break


res = 0
rest = set()
for i in range(1,n+1):
    rest.add(i)
for x in z1:
    rest -= x
for x in rest:
    if x == p[x-1]:res += 1
for x in z1:
    for y in x:
        if p[y-1] in x:res += 1


print(res)

Submission status: Wrong Answer

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

save = [set()]
for i in range(m):
    x,y = list(map(int,input().split()))
    for z in save:
        if z == set():
            z.add(x)
            z.add(y)
            save.append(set())
            break
        else:
            if x in z or y in z:
                z.add(x)
                z.add(y)
                break

z1 = [set()]

for x in save:
    if x == set():
        break
    for y in range(len(z1)):
        if z1[y] == set():
            z1[y] = x
            z1.append(set())
            break
        else:
            if x & z1[y] != set():
                z1[y] = x | z1[y]
                break


res = 0

for i in range(1,n+1):
    if i == p[i-1]:
        res += 1
        continue
    else:
        for x in z1:
            if i in x and p[i-1] in x:
                res += 1
                break

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
arr = list(map(int,input().split()))
s= set()
d = {i:-1 for i in range(N)}
p = {i:[] for i in range(M)}
kind = 0
for i in range(M):
    a,b = map(int,input().split())
    if (not (a in s)) and (not(b in s)):
        s.add(a)
        s.add(b)
        d[a-1] = kind
        d[b-1] = kind
        kind += 1
    else:
        if a in s:
            if d[b-1] == -1:
                d[b-1] = d[a-1]
            else:
                p[d[b-1]].append(d[a-1])
                p[d[a-1]].append(d[b-1])

        else:
            if d[a-1] == -1:
                d[a-1] = d[b-1]
            else:
                p[d[a-1]].append(d[b-1])
                p[d[b-1]].append(d[a-1])
#print(p)
#print(d)
out = 0
for i in range(N):
    if d[arr[i]-1] == -1:
        if arr[i] == i+1:
            out += 1
    elif d[arr[i]-1] == d[i] or  (d[i] != -1 and d[arr[i]-1] in p[d[i]]):
        #print(d[arr[i]-1],d[i],p[d[i]])
        out += 1

print(out)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [set(map(int,input().split())) for i in [None]*M]

LSET = L[:]
LSET2 = []
i = 0
while i < len(LSET):
    tmp = LSET[i]
    if not tmp:
        i += 1
        continue
    j = i + 1
    while j < len(LSET):
        if  LSET[j] and not tmp.isdisjoint(LSET[j]):
            tmp |= LSET[j]
            LSET[j] = None
        j += 1
    LSET2.append(tmp)
    i += 1
LSET = LSET2[:]

result = len([i for i in set(range(1,N+1)).difference(*LSET) if i == P[i-1]])
result += sum([ len({P[i-1] for i in s} & s )for s in LSET])
#result += sum([len(l&p) for l,p in zip(LSET,PSET)])
print(result)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [set(map(int,input().split())) for i in [None]*M]

LSET = L[:]
LSET2 = []
i = 0
while i < len(LSET):
    tmp = LSET[i]
    if not tmp:
        i += 1
        continue
    j = i + 1
    while j < len(LSET):
        if  LSET[j] and not tmp.isdisjoint(LSET[j]):
            tmp |= LSET[j]
            LSET[j] = None
        j += 1
    LSET2.append(tmp)
    i += 1
LSET = LSET2[:]

result = len([i for i in set(range(1,N+1)).difference(*LSET) if i == P[i-1]]) + sum([len({P[i-1] for i in s}&s)for s in LSET])
print(result)

Submission status: Wrong Answer

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

pList = input().split()
pairList = []

indexList = [0 for _ in range(N+1)]
groupNum = 1
for i in range(M):
    thisPair = input().split()
    p1 = int(thisPair[0])
    p2 = int(thisPair[1])
    if indexList[p1] == 0 and indexList[p2] == 0:
        indexList[p1] = groupNum
        indexList[p2] = groupNum
        groupNum += 1
    elif indexList[p1] == 0 and indexList[p2] != 0:
        indexList[p1] = indexList[p2]
    elif indexList[p1] != 0 and indexList[p2] == 0:
        indexList[p2] = indexList[p1]
    else:
        unifiedGroup = indexList[p1]
        for i in range(len(indexList)):
            if indexList[i] == unifiedGroup:
                indexList[i] = indexList[p2]
    # print(indexList)


groupMap = {}
for i in range(len(indexList)):
    if str(indexList[i]) in groupMap.keys():
        groupMap[str(indexList[i])].append(i)
    else:
        groupMap[str(indexList[i])] = [i]
# print(pList)
# print(groupMap)
# print(indexList)
res = 0
for i in range(1,len(pList)+1):
    if i == int(pList[i-1]):
        # print(i)
        res += 1
    else:
        groupName = str(indexList[i])
        if i in groupMap[groupName] and int(pList[i-1]) in groupMap[groupName]:
            # print(i, 'a')
            res += 1
print(res)

Submission status: Wrong Answer

Solution code:
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            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 connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
N,M = map(int,input().split())
tree = Unionfindtree(N)
P =[int(i) for i in input().split()]
for i in range(M):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)
    
ans = 0
for i in range(N):
    if tree.connect(P[i]-1,i):
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
p=i2()

import sys
sys.setrecursionlimit(10000)

par=[i for i in range(n)]
rank=[0 for i in range(n)]

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

def un(x,y):
    x=rt(x)
    y=rt(y)
    if x==y:
       return
    else:
       if rank[x]<rank[y]:
          par[x]=y
       else:
          par[y]=x
          if rank[x]==rank[y]:
             rank[x]+=1
xy=[]
for i in range(m):
 xy.append(i2())
 xy.append([xy[-1][1],xy[-1][0]])
xy.sort()
for i,j in xy:
 un(i-1,j-1)
s=0
for i in range(n):
 if par[i]==par[p[i]-1]:
   s+=1
print(s)

Submission status: Wrong Answer

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

l = [-1 for _ in range(n)]
gn = 0
g = []

for _ in range(m):
    x,y = map(int, input().split())
    if l[x-1] == -1 and l[y-1] == -1:
        l[x-1] += 1 + gn
        l[y-1] += 1 + gn
        g.append([x,y])
        gn += 1
    elif l[x-1] != -1 and l[y-1] != -1:
        pass
    else:
        if l[x-1] == -1:
            l[x-1] = l[y-1]
            g[l[y-1]].append(x)
        else:
            l[y-1] = l[x-1]
            g[l[x-1]].append(y)

ans = 0
for i in range(n):
    if p[i] == i+1:
        ans += 1
    else:
        if l[i] != -1:
            if p[i] in g[l[i]]:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:


class Board:

    # マス目の数字に島を対応させるdict
    # マージを楽にするため2段になっている
    # m[h[(マス目の数字]] = 島番号
    h = {}
    m = {}

    island = 0  # 現在の島番号

    # hが指す島に新しいマス目を追加する
    def add(self, h, new_item):
        self.h[new_item] = h

    # 2つの島をまとめてひとつにする
    def merge(self, h1, h2):
        self.m[h2] = self.m[h1]

    # 既存の島とつながっていない道が追加されたので新しい島を作って対応させる
    def new_pair(self, x, y):
        new_h = len(self.m) + 1
        self.island += 1

        self.h[x] = new_h
        self.h[y] = new_h
        self.m[new_h] = self.island

    # x, yの間に道を追加する
    def add_pair(self, x, y):
        # x, yが既にある島に含まれるかどうかで場合分け
        if x in self.h:
            h_x = self.h[x]
            if y in self.h:
                h_y = self.h[y]
                if self.m[h_x] == self.m[h_y]:
                    pass
                else:
                    self.merge(h_x, h_y)
            else:
                self.add(h_x, y)
        else:
            if y in self.h:
                self.add(self.h[y], x)
            else:
                self.new_pair(x, y)

    # iからjに移動できるかどうか判定
    def movable(self, i, j):
        return i == j \
               or (i in self.h and j in self.h and self.m[self.h[i]] == self.m[self.h[j]])

    def equals(self, *tips):
        result = 0

        for i, x in enumerate(tips):
            if self.movable(i+1, x):
                result += 1

        return result


def main():
    n, m = map(int, input().split())
    tips = map(int, input().split())
    board = Board()
    for i in range(m):
        pair = map(int, input().split())
        board.add_pair(*pair)
    print("{0:d}".format(board.equals(*tips)))


main()

Submission status: Wrong Answer

Solution code:


class Board:

    # マス目の数字に島を対応させるdict
    # マージを楽にするため2段になっている
    # m[h[(マス目の数字]] = 島番号
    h = {}
    m = {}

    island = 0  # 現在の島番号

    # hが指す島に新しいマス目を追加する
    def add(self, h, new_item):
        self.h[new_item] = h

    # 2つの島をまとめてひとつにする
    def merge(self, h1, h2):
        self.m[h2] = self.m[h1]

    # 既存の島とつながっていない道が追加されたので新しい島を作って対応させる
    def new_pair(self, x, y):
        new_h = len(self.m) + 1
        self.island += 1

        self.h[x] = new_h
        self.h[y] = new_h
        self.m[new_h] = self.island

    # x, yの間に道を追加する
    def add_pair(self, x, y):
        # x, yが既にある島に含まれるかどうかで場合分け
        if x in self.h:
            h_x = self.h[x]
            if y in self.h:
                h_y = self.h[y]
                if self.m[h_x] == self.m[h_y]:
                    pass
                else:
                    self.merge(h_x, h_y)
            else:
                self.add(h_x, y)
        else:
            if y in self.h:
                self.add(self.h[y], x)
            else:
                self.new_pair(x, y)

    # iからjに移動できるかどうか判定
    def movable(self, i, j):
        return i == j \
               or (i in self.h and j in self.h and self.m[self.h[i]] == self.m[self.h[j]])

    def equals(self, *tips):
        result = 0

        for i, x in enumerate(tips):
            if self.movable(i, x):
                result += 1

        return result


def main():
    n, m = map(int, input().split())
    tips = map(int, input().split())
    board = Board()
    for i in range(m):
        pair = map(int, input().split())
        board.add_pair(*pair)
    print("{0:d}".format(board.equals(*tips)))


main()

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
p=list(map(int, input().split()))
q=list()
for i in range(m):
    q.append(set(map(int, input().split())))
count=0
while count!=10000:
    a=q.pop()
    for j in q:
        if len(j&a) != 0:
            j |=a
            count=0
            break
    else:q=[a]+q
    if count>len(q): break
    count+=1
    
count2=0
for i in q:
    r=list()
    for j in list(i):
        r.append(p[j-1])
    #print(i,r)
    count2 += len(i&set(r))
print(count2)

Submission status: Wrong Answer

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

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

groups = [{xy[0]:0, xy[1]:0}]

for i in range(1, m):
    xy = list(map(int, input().split()))
    for j in range(len(groups)):
        if(xy[0] in groups[j] or xy[1] in groups[j]):
            groups[j][xy[0]] = 0
            groups[j][xy[1]] = 0
            break
    else:
        groups.append({xy[0]:0, xy[1]:0})

ngroups = []

for i in range(len(groups)):
    if(len(ngroups) == 0):
        ngroups.append(groups[i])
    exist = False
    for j in range(len(ngroups)):
        keys = groups[i]
        for k in keys:
            if k in ngroups[j]:
                ngroups[j].update(groups[i])
                exist = True
                break
        if(exist):
            break
count = 0
for i in range(len(p)):
    exist = False
    for j in ngroups:
        if((i + 1) in j and p[i] in j):
            count += 1
            break
    else:
        if p[i] == i + 1:
            count += 1

print(count)

Submission status: Wrong Answer

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

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

groups = [{xy[0]:0, xy[1]:0}]

for i in range(1, m):
    xy = list(map(int, input().split()))
    for j in range(len(groups)):
        if(xy[0] in groups[j] or xy[1] in groups[j]):
            groups[j][xy[0]] = 0
            groups[j][xy[1]] = 0
            break
    else:
        groups.append({xy[0]:0, xy[1]:0})

ngroups = []

for i in range(len(groups)):
    if(len(ngroups) == 0):
        ngroups.append(groups[i])
    exist = False
    for j in range(len(ngroups)):
        keys = groups[i]
        for k in keys:
            if k in ngroups[j]:
                ngroups[j].update(groups[i])
                exist = True
                break
        if(exist):
            break
count = 0
for i in range(len(p)):
    exist = False
    for j in ngroups:
        if((i + 1) in j and p[i] in j):
            count += 1
            exist = True
            break
    if exist == False and p[1] == i + 1:
        count+= 1

print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p  = list(map(int, input().split()))
group = [-1] * (n+1)
member = []
for i in range(m):
    x, y = map(int, input().split())
    if group[x] == -1 and group[y] == -1:
        #addnewgroup
        member.append({x,y})
        group[x] = group[y] = len(member) - 1
    elif group[x] == -1:
        group[x] = group[y]
        member[group[x]].add(x)
    elif group[y] == -1:
        group[y] = group[x]
        member[group[x]].add(y)
    elif group[x] != group[y]:
            old = group[y]
            member[group[x]] |= member[group[y]]
            group[y] = group[x]
            member[old].clear()

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

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
def main():
	n, m = list(map(int, input().split()))
	ps = list(map(int, input().split()))
	xs = [list(map(int, input().split())) for _ in range(m)]

	d = {}

	for x in xs:
		if x[0] in d.keys():
			d[x[0]].append(x[1])
		else:
			d[x[0]] = [x[1]]

		if x[1] in d.keys():
			d[x[1]].append(x[0])
		else:
			d[x[1]] = [x[0]]

	subsets = []
	while True:
		start = list(d.keys())[0]
		tmp = d[start]
		del d[start]

		i = 0
		while True:
			if i < len(tmp):
				if tmp[i] in d.keys():
					tmp2 = d[tmp[i]]
					del d[tmp[i]]
					for x in tmp2:
						if x not in tmp:
							tmp.append(x)
			else:
				break
			i += 1

		subsets.append(tmp)

		if len(d.keys()) == 0:
			break

	values = []
	for i in range(len(subsets)):
		value = []
		for x in subsets[i]:
			value.append(ps[x-1])
		values.append(value)

	ans = 0

	for i in range(len(subsets)):
		ans += len(set(subsets[i]).intersection(set(values[i])))

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

groups = [{xy[0]:0, xy[1]:0}]

for i in range(1, m):
    xy = list(map(int, input().split()))
    for j in range(len(groups)):
        if(xy[0] in groups[j] or xy[1] in groups[j]):
            groups[j][xy[0]] = 0
            groups[j][xy[1]] = 0
            break
    else:
        groups.append({xy[0]:0, xy[1]:0})

ngroups = []

for i in range(len(groups)):
    if(len(ngroups) == 0):
        ngroups.append(groups[i])
    exist = False
    for j in range(len(ngroups)):
        keys = groups[i]
        for k in keys:
            if k in ngroups[j]:
                ngroups[j].update(groups[i])
                exist = True
                break
        if(exist):
            break
count = 0
for i in range(len(p)):
    for j in ngroups:
        if((i + 1) in j and p[i] in j):
            count += 1

for i in range(len(p)):
    exist = False
    for j in range(len(ngroups)):
        if(p[j] in groups[j]):
            exist = True
            break
    if exist == False and p[1] == i + 1:
        count+= 1
print(count)

Submission status: Wrong Answer

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

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

groups = [{xy[0]:0, xy[1]:0}]

for i in range(1, m):
    xy = list(map(int, input().split()))
    for j in range(len(groups)):
        if(xy[0] in groups[j] or xy[1] in groups[j]):
            groups[j][xy[0]] = 0
            groups[j][xy[1]] = 0
            break
    else:
        groups.append({xy[0]:0, xy[1]:0})

ngroups = []

for i in range(len(groups)):
    if(len(ngroups) == 0):
        ngroups.append(groups[i])
    exist = False
    for j in range(len(ngroups)):
        keys = groups[i]
        for k in keys:
            if k in ngroups[j]:
                ngroups[j].update(groups[i])
                exist = True
                break
        if(exist):
            break
count = 0
for i in range(len(p)):
    for j in ngroups:
        if((i + 1) in j and p[i] in j):
            count += 1

for i in range(len(p)):
    exist = False
    for j in range(len(ngroups)):
        if(p[j] == j):
            exist = True
            break
    if exist == False and p[1] == i + 1:
        count+= 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p  = list(map(int, input().split()))
group = [-1] * (n+1)
member = []
for i in range(m):
    x, y = map(int, input().split())
    if group[x] == -1 and group[y] == -1:
        #addnewgroup
        member.append({x,y})
        group[x] = group[y] = len(member) - 1
    elif group[x] == -1:
        group[x] = group[y]
        member[group[x]].add(x)
    elif group[y] == -1:
        group[y] = group[x]
        member[group[x]].add(y)
    elif group[x] != group[y]:
            old = group[y]
            group[y] = group[x]
            member[group[x]] |= member[group[y]]
            member[old].clear()

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

Submission status: Wrong Answer

Solution code:
# n = int(input())
# a, b = map(int, input().split())
# c = list(map(int, input().split()))
# d = [list(map(int, input().split())) for _ in range(n)]



N, M = map(int, input().split())
p = list(map(int, input().split()))
swap = [list(map(int, input().split())) for _ in range(M)]
group = []
find = False

for swap_i in swap:
    find = False
    for group_i in group:
        if swap_i[0] in group_i:
            group_i.add(swap_i[1])
            find = True
        if swap_i[1] in group_i:
            group_i.add(swap_i[0])
            find = True

    if find:
        continue
    else:
        tmp = set()
        tmp.add(swap_i[0])
        tmp.add(swap_i[1])
        group.append(tmp)


for i in range(1, N+1):
    findednot = True
    for group_i in group:
        if i in group_i:
            findednot = False
            break
    if findednot:
        tmp = set()
        tmp.add(i)
        group.append(tmp)


ans = 0

for i in range(1, N+1):
    for group_i in group:
        if i in group_i:
            if p[i-1] in group_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()))

groups = [{xy[0]:0, xy[1]:0}]

for i in range(1, m):
    xy = list(map(int, input().split()))
    for j in range(len(groups)):
        if(xy[0] in groups[j] or xy[1] in groups[j]):
            groups[j][xy[0]] = 0
            groups[j][xy[1]] = 0
            break
    else:
        groups.append({xy[0]:0, xy[1]:0})

ngroups = []

for i in range(len(groups)):
    if(len(ngroups) == 0):
        ngroups.append(groups[i])
    exist = False
    for j in range(len(ngroups)):
        keys = groups[i]
        for k in keys:
            if k in ngroups[j]:
                ngroups[j].update(groups[i])
                exist = True
                break
        if(exist):
            break
count = 0
for i in range(len(p)):
    for j in ngroups:
        if((i + 1) in j and p[i] in j):
            count += 1

print(count)

Submission status: Wrong Answer

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

G = []
nolinks = list(range(1,N+1))
for pair in pairs:
    x, y = pair
    if x in nolinks:
        nolinks.remove(x)
    if y in nolinks:
        nolinks.remove(y)

    g_x = -1
    g_y = -1
    for i in range(len(G)):
        if x in G[i]:
            g_x = i
        if y in G[i]:
            g_y = i
    if g_x>-1:
        if g_y>-1:
            G[g_x] += G[g_y]
            del G[g_y]
        else:
            G[g_x].append(y)
    elif g_y>-1:
        G[g_y].append(x)
    else:
        G.append([x,y])
#print(G)
#print(nolinks)

cnt = 0
for g in G:
    for i in g:
        if P[i-1] in g:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = input().split( )
N = int(n[0])
M = int(n[1])
p = list(map(int, input().split()))

c =[]
for m in range(M):
    o = list(map(int, input().split()))
    k = 0
    b = []
    x=0
    if m == 0:
        c.append(o)
    else:
        for i in range(len(c)):
            
            if o[0] in c[i]:
                k += 1
                b.append(i)
            if o[1] in c[i]:
                k += 1
                x=1
                b.append(i)

        if k == 0:
            c.append(o)
        elif k == 1:
            if x==0:
                c[i].append(o[1])
            else:
                c[i].append(o[0])
        elif k == 2:
            c[b[0]]+=c[b[1]]
            del c[b[1]]

l = 0

for i in range(len(p)):
    if p[i] == i+1:
        l += 1
    else:
        for j in c:  
            if (i+1 in j) and (p[i] in j):
                l+=1
        
print(l)

Submission status: Wrong Answer

Solution code:
n = input().split( )
N = int(n[0])
M = int(n[1])
p = list(map(int, input().split()))

c =[]
for m in range(M):
    o = list(map(int, input().split()))
    k = 0
    b = []
    x=0
    if m == 0:
        c.append(o)
    else:
        for i in range(len(c)):
            
            if o[0] in c[i]:
                k += 1
                b.append(i)
            if o[1] in c[i]:
                k += 1
                x=1
                b.append(i)

        if k == 0:
            c.append(o)
        elif k == 1:
            if x==0:
                c[i].append(o[1])
            else:
                c[i].append(o[0])
        elif k == 2:
            c[b[0]]+=c[b[1]]
            del c[b[1]]

l = 0

for i in range(len(c)):
    for j in range(len(c[i])):
  
        if p[c[i][j]-1] in c[i]:
            l+=1
        
print(l)

Submission status: Wrong Answer

Solution code:
ALPHA = "abcdefghijklmnopqrstuvwxyz"


def solve(pi, tuples):
    connects_sets = []
    for x, y in tuples:
        f = False
        for i, s in enumerate(connects_sets):
            if x in s or y in s:
                s.add(x)
                s.add(y)
                f = True
                break
        if not f:
            s = set()
            s.add(x)
            s.add(y)
            connects_sets.append(s)

    connects_sets_new = []
    added = set()
    for i, s1 in enumerate(connects_sets):
        if i in added:
            continue
        flag = True
        for j, s2 in enumerate(connects_sets[i + 1:]):
            if len(s1.intersection(s2)) != 0:
                connects_sets_new.append(s1.union(s2))
                flag = False
                added.add(i)
                added.add(j + i + 1)
                break
        if flag:
            connects_sets_new.append(s1)
            added.add(i)

    all_set = set()
    for s in connects_sets_new:
        all_set = all_set.union(s)
    leave = []
    for n in range(len(pi)):
        nn = n + 1
        if nn not in all_set:
            leave.append(nn)

    res = 0
    for l in leave:
        if l == pi[l-1]:
            res += 1

    for s in connects_sets_new:
        indexies = set([pi[i - 1] for i in s])
        inter = indexies.intersection(s)
        res += len(inter)
    return res


def main():
    N, M = [int(a) for a in input().split()]
    pi = [int(a) for a in input().split()]
    tuples = [[int(a) for a in input().split()] for _ in range(M)]
    res = solve(pi, tuples)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:


class UnionFind:

    def __init__(self):
        self.p = {}
        self.r = {}

    def root(self, x):
        if x not in self.p:
            self.p[x] = x
            self.r[x] = 0
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] == self.r[y]:
            self.r[x] += 1
        elif self.r[x] > self.r[y]:
            x, y = y, x
        self.p[x] = y

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

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind()
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()