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: Time Limit Exceeded

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

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

Swap=[None]*M

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break

        if judge_2==0:
            i+=1
        else:
            judge_2=0


Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break

        if judge_2==0:
            i+=1
        else:
            judge_2=0

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

Other=list(Other)

count=0

for i in range(finish):
    for j in list(Swap[i]):
        if P[j-1] in Swap[i]:
            count+=1    

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break
            
        #print(i,finish,judge,Swap)

        if judge_2==0:
            i+=1
        else:
            judge_2=0
        

#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(finish):
    for j in list(Swap[i]):
        if P[j-1] in Swap[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=[1 for i in range(M)]

Y[0]=Y[0]|Swap[0]
Unstacked[0]=0
j=0
k=0

while True:
    while j<M:
        if Unstacked[j]==0:
            j+=1
            continue

        if Y[k] & Swap[j] !=set():

            Y[k]=Y[k]|Swap[j]
            Unstacked[j]=0
            j=0

        elif j <M-2:
            j+=1

        else: break

    if 1 in Unstacked:
        
        k+=1
        Y[k]=Swap[Unstacked.index(1)]
        j=0

    else:
        break

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=[1 for i in range(M)]

Y[0]=Y[0]|Swap[0]
Unstacked[0]=0
j=0
k=0

while True:
    while j<M:
        if Unstacked[j]==0:
            j+=1
            continue

        if Y[k] & Swap[j] !=set():

            Y[k]=Y[k]|Swap[j]
            Unstacked[j]=0
            j=0
            #print(Y,j,Unstacked)

        elif j <M-2:
            j+=1

        else: break

    if 1 in Unstacked:
        
        k+=1
        Y[k]=Swap[Unstacked.index(1)]
        j=0

    else:
        break


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while True:
    while Unstacked !=[]:
        s=Unstacked[j]

        if Y[k] & Swap[s] !=set():

            Y[k]=Y[k]|Swap[s]
            del Unstacked[j]
            #print(Y,j,Unstacked)
            j=0

        elif j <len(Unstacked)-1:
            j+=1

        else: break

    if Unstacked != []:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])
        j=0

    else:
        break


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while Unstacked!=[]:
    while j <len(Unstacked):

        if Y[k] & Swap[Unstacked[j]] !=set():

            Y[k]=Y[k]|Swap[Unstacked[j]]
            Unstacked.remove(Unstacked[j])
            j=0

        else:
            j+=1

    if Unstacked!=[]:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while Unstacked!=[]:
    while j <len(Unstacked):

        if Y[k] & Swap[Unstacked[j]] !=set():

            Y[k]=Y[k]|Swap[Unstacked[j]]
            Unstacked.remove(Unstacked[j])
            #print(Y,j,Unstacked)
            j=0

        else:
            j+=1

    if Unstacked!=[]:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# UnionFindで参考にしたページ
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html


# 集合の代表を求める
def find(x):
    while link[x] >= 0:
        x = link[x]
    return x


# 併合
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            # 小さいほうが個数が多い
            link[s1] += link[s2]
            link[s2] = s1
        else:
            link[s2] += link[s1]
            link[s1] = s2
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

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

cnt = 0
for i in range(1, N + 1):
    a = find(i)
    b = find(p[i - 1])
    if a == b:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

result = 0

p = list(map(int, input().split()))
xy = []
for i in range(M):
    xy.append(set(map(int, input().split())))

for num in range(1, N+1):
  if num == p[num-1]:
    result += 1
    p[num-1] = 0
  
  tmp = []
  for lis in xy[:]:
    if num in lis:
      tmp.extend(lis)
      xy.remove(lis)
  if tmp:
    xy.append(list(set(tmp)))

for lis in xy:
  tmp = []
  for l in lis:
    tmp.append(p[l-1])
  for l in lis:
    if l in tmp:
      result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
            cGT.append(e[1])
        elif e[1] in c:
            aru = True
            c.append(e[0])
            cGT.append(e[0])
    if not aru:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
res = 0
for i in list(set(p) - cGT):
    if p[i - 1] == i:
        res = res + 1

for i in cGT:
    for c in cG:
        if i in c:
            if p.index(i) + 1 in c:
                res = res + 1
                break
print(res)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
            cGT.append(e[1])
        elif e[1] in c:
            aru = True
            c.append(e[0])
            cGT.append(e[0])
    if not aru:
        cG.append(e)
        cGT = cGT + e

cGT = set(cGT)
cant = list(set(p) - cGT)
res = 0
for i in cant:
    if p[i - 1] == i:
        res = res + 1

for i in cGT:
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
cGT = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
            cGT.append(e[1])
        elif e[1] in c:
            aru = True
            c.append(e[0])
            cGT.append(e[0])
    if not aru:
        cG.append(e)
        cGT = cGT + e

cant = list(set(p) - set(cGT))
res = 0
for i in cant:
    if p[i - 1] == i:
        res = res + 1

for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

res = 0
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        if p[i - 1] == i:
            res = res + 1

for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
cG = []
for i in range(0, m):
    e = list(map(int, input().split()))
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1

for i in cant:
    if p[i - 1] == i:
        res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)
  
  ans = 0
  for lst in belongs:
    for i in lst:
      if plst[i] - 1 in lst:
        ans += 1
  
  print(ans)
solve()

Submission status: Time Limit Exceeded

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

def get_root(x):
  p = pare_inds[x]
  if p == x:
    return x
  a = get_root(p)
  pare_inds[x] = a
  return a
#def get_root(x):
#  lst = []
#  while pare_inds[x] != x:
#    lst.append(x)
#    x = pare_inds[x]
#  for i in lst:
#    pare_inds[i] = x
#  return x
#
for i in range(m):
  x, y = map(int,input().split())
  x, y = x - 1, y - 1
  r_x, r_y  = get_root(x), get_root(y)
  if r_x < r_y:
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  elif r_x > r_y:
    pare_inds[x] = r_y
    pare_inds[r_x] = r_y
#  print(x,y,p_x,p_y,pare_inds)

for i in range(n):
  belongs[get_root(i)].append(i)

ans = 0
for lst in belongs:
  for i in lst:
    if plst[i] - 1 in lst:
      ans += 1

print(ans)
#print(belongs)
#print(pare_inds)

Submission status: Time Limit Exceeded

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

def get_root(x):
  lst = []
  while pare_inds[x] != x:
    lst.append(x)
    x = pare_inds[x]
  for i in lst:
    pare_inds[i] = x
  return x

for i in range(m):
  x, y = map(int,input().split())
  x, y = x - 1, y - 1
  r_x, r_y  = get_root(x), get_root(y)
  if r_x < r_y:
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  elif r_x > r_y:
    pare_inds[x] = r_y
    pare_inds[r_x] = r_y
#  print(x,y,p_x,p_y,pare_inds)

for i in range(n):
  belongs[get_root(i)].append(i)

ans = 0
for lst in belongs:
  for i in lst:
    if plst[i] - 1 in lst:
      ans += 1

print(ans)
#print(belongs)
#print(pare_inds)

Submission status: Time Limit Exceeded

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

def get_root(x):
  while pare_inds[x] != x:
    x = pare_inds[x]
  return x

for i in range(m):
  x, y = map(int,input().split())
  x, y = x - 1, y - 1
  p_x, p_y  = get_root(x), get_root(y)
  if p_x < p_y:
    pare_inds[y] = p_x
    pare_inds[p_y] = p_x
  elif p_x > p_y:
    pare_inds[x] = p_y
    pare_inds[p_x] = p_y
#  print(x,y,p_x,p_y,pare_inds)

for i in range(n):
  belongs[get_root(i)].append(i)

ans = 0
for lst in belongs:
  for i in lst:
    if plst[i] - 1 in lst:
      ans += 1

print(ans)
#print(belongs)
#print(pare_inds)

Submission status: Time Limit Exceeded

Solution code:
def dfs(graph, start, end):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)
            # __logging(visited, stack)
            return True
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
        #__logging(visited, stack)
    return False
    
N,M = map(int,input().split())

tmp = list(map(int,input().split()))
nums = [0] + tmp

X_Y = {}
for i in range(M):
	tmp = list(map(int,input().split()))
	X_Y.setdefault(tmp[0], []).append(tmp[1])
	X_Y.setdefault(tmp[1], []).append(tmp[0])
length = len(nums)-1

soeji = [0] + [nums.index(i) for i in range(1,length+1)]
ans = 0
for i in range(1,N+1):
	if i == soeji[i] or dfs(X_Y,i,soeji[i]):
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
p = inpl()
graph = {}
for i in range(1, N+1):
    graph[i] = []
for i in range(M):
    x,y = inpl()
    graph[x].append(y)
    graph[y].append(x)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

group = [list(x) for x in connected_components(graph)]

ans = 0
for g_i in group:
    a = 0
    for j in g_i:
        if p[j-1] in g_i:
            a += 1
    ans += a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for j in range(m)]

x_ = deepcopy(x)
tree = []
memo = []

try:
    for i, y in enumerate(x_):
        if y in memo:
            continue
        tree.append(set(y))
        while True:
            prev = tree[i]
            for j in x_[i+1:]:
                if tree[i] & set(j):
                    tree[i] = tree[i] | set(j)
                    memo.append(j)

            if not tree[i] - prev:
                break
except:
    pass

for i in tree:
    i = list(i)
    temp = [p[j-1] for j in i]
    for j in i:
        if j in temp:
            p[j-1] = j

ans = 0

for i, p_ in enumerate(p):
    if i+1 == p_:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = list(map(int, sys.stdin.readline().strip().split()))
ps = list(map(int, sys.stdin.readline().strip().split()))

reps = []
for i in range(M):
    reps.append(list(map(int, sys.stdin.readline().strip().split())))

# print(N, M)
# print(ps)
# print(reps)

def search(path, goal, ops, used):
    # print(path, goal)
    cur = path[-1]
    if cur == goal:
        return True

    r = False
    for op in ops:
        if op[0] == cur and op[1] not in used:
            used.add(op[1])
            r = search(path + [op[1]], goal, ops, used)
            if r: return r
        if op[1] == cur and op[0] not in used:
            used.add(op[0])
            r = search(path + [op[0]], goal, ops, used)
            if r: return r
    return r

cnt = 0
for i in range(N):
    x = ps[i]
    if search([i+1], x, reps, set()):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
pairs = []
for i in range(0, m):
    pairs.append(list(map(int, input().split())))
cG = []
for e in pairs:
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for i in range(1, n + 1):
    for c in cG:
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1
    if i in cant:
        if p[i - 1] == i:
            res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(a) for a in input().split()]
num_suc = [int(a) for a in input().split()]
swap_list = []
for i in range(M):
    new_one = [int(a)-1 for a in input().split()]
    ald_list = [a for a in swap_list if new_one[0] in a or new_one[1] in a]
    if len(ald_list) == 0:
        swap_list.append(new_one)
    elif len(ald_list) == 1:
        swap_list.remove(ald_list[0])
        add_one = list(set(ald_list[0] + new_one))
        swap_list.append(add_one)
    else:
        swap_list.remove(ald_list[0])
        swap_list.remove(ald_list[1])
        add_one = list(set(ald_list[0] + ald_list[1]))
        swap_list.append(add_one)

aa = [i for i in range(N) if i == num_suc.index(i+1) or (len([a for a in swap_list if num_suc.index(i+1) in a])>0 and i in [a for a in swap_list if num_suc.index(i+1) in a][0])]
print(str(len(aa)))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,m = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
c,d,e = [[] for i in range(n+1)],[True for i in range(n+1)],[]
d[0],ans = False,0
for i,j in x:
	c[i].append(j)
	c[j].append(i)
while sum(d)!=0:
	for i in range(n+1):
		if d[i]: break
	num2,numx,d[i] = set([i]),[i],False
	while True:
		num3 = set([])
		for i2 in list(num2):
			for j in c[i2]:
				if d[j]:
					num3.add(j)
					d[j] = False
		if len(num3)==0: break
		else:
			num2,num3 = deepcopy(num3),set([])
			for i in num2: numx.append(i)
	e.append(numx)
for i in e:
	for j in i:
		if p[j-1] in i: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for _ in range(M)]


nums_set = []
for i in range(1, N+1):
    flg = 1
    for numset in nums_set:
        if i in numset:
            flg = 0
            break
    if flg:
        numset = set()
        numset.add(i)
        flg = 1
        while True:
            previous = len(numset)
            for x, y in xy:
                if x in numset and y not in numset:
                    numset.add(y)
                    flg = 0
                elif y in numset and x not in numset:
                    numset.add(x)
                    flg = 0
            if len(numset) == previous:
                break
        nums_set.append(numset)

ans = 0
for numset in nums_set:
    p_list = [p[i-1] for i in numset]
    for i in numset:
        if i in p_list:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    root[x].append(y)
    root[y].append(x)
    
can_move = [[i] for i in range(n+1)]

for i in range(1, n+1):
    heap = root[i].copy()
    while len(heap):
        v = heap[0]
        if v == p[i-1] or p[i-1] in root[v]:
            can_move[i].append(p[i-1])
            break
        
        for t in root[v]:
            if t not in can_move[i] and i != t:
                can_move[i].append(t)
                heap.append(t)
        heap.pop(0)

cnt = 0
for i, pi in enumerate(p):
    if pi in can_move[i+1]:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
(n, m) = list(map(int, input().split()))
p = list(map(int, input().split()))
pairs = []
for i in range(0, m):
    pairs.append(list(map(int, input().split())))
cG = []
for e in pairs:
    aru = False
    do = []
    for c in cG:
        if e[0] in c or e[1] in c:
            if not do == []:
                mix = do + c
                cG.remove(do)
                cG.remove(c)
                cG.append(mix)
                break
            else:
                do = c
        if e[0] in c:
            aru = True
            c.append(e[1])
        if e[1] in c:
            aru = True
            c.append(e[0])
    if not aru:
        cG.append(e)

cant = []
for i in range(1, n + 1):
    cc = False
    for c in cG:
        if i in c:
            cc = True
            break
    if not cc:
        cant.append(i)

res = 0
for c in cG:
    for i in range(1, n + 1):
        if i in c:
            ku = p.index(i) + 1
            if ku in c:
                res = res + 1

for i in cant:
    if p[i - 1] == i:
        res = res + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,raw_input().split(' '))
p=map(int,raw_input().split(' '))

gr=[]
for _ in range(M):
  x,y=map(int,raw_input().split(' '))
  if len(gr)==0:
    gr.append(set([x,y]))
  else:
    flg=1
    for i in range(len(gr)):
      if x in gr[i] or y in gr[i]:
        gr[i]=gr[i]|set([x,y])
        flg=0
    if flg:
      gr.append(set([x,y]))

def check(g):
  for i in range(len(g)):
    for j in range(i+1,len(g)):
      if len(g[i]&g[j])>0:
        return 0
  return 1

while not check(gr):
  flg=1
  i=0
  while flg:
    for j in range(i+1,len(gr)):
      if len(gr[i]&gr[j])>0:
        gr[i]=gr[i]|gr[j]
        del gr[j]
        flg=0
        break

r_=0
for i in range(len(p)):
  if i==p[i]-1:
    r_+=1

r=0
for g in gr:
  s=set()
  for n in g:
    s.add(p[n-1])
  r += len(g&s)

print max(r,r_)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(a) for a in input().split()]
num_suc = [int(a) for a in input().split()]
swap_list = []
for i in range(M):
    new_one = [int(a)-1 for a in input().split()]
    ald_list = [a for a in swap_list if new_one[0] in a or new_one[1] in a]
    if len(ald_list) == 0:
        swap_list.append(new_one)
    elif len(ald_list) == 1:
        swap_list.remove(ald_list[0])
        add_one = list(set(ald_list[0] + new_one))
        swap_list.append(add_one)
    else:
        swap_list.remove(ald_list[0])
        swap_list.remove(ald_list[1])
        add_one = list(set(ald_list[0] + ald_list[1]))
        swap_list.append(add_one)
ans = 0
for i in range(N):
    place = num_suc.index(i+1)
    eneble_list = [a for a in swap_list if place in a]
    if len(eneble_list) == 0:
        eneble_list = [[place]]
    if i in eneble_list[0]:
        ans += 1

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

N, M = read_line(int, int)

p = [int(s) - 1 for s in input().split()]
p0 = list(range(N))

pairs = [read_line(int, int) for _ in range(M)]
pairs = [sorted([pair[0] - 1, pair[1] - 1]) for pair in pairs]

# print(p)
# print(p0)
# print(pairs)

flag = True
while flag:
    flag = False
    additional_pairs = []
    for pair1  in pairs:
        for pair2 in pairs:
            if pair1 != pair2:
                if pair1[0] == pair2[0]:
                    if [pair1[1], pair2[1]] not in (pairs + additional_pairs):
                        additional_pairs.append([pair1[1], pair2[1]])
                        flag = True
                if pair1[1] == pair2[1]:
                    if [pair1[0], pair2[0]] not in (pairs + additional_pairs):
                        additional_pairs.append([pair1[0], pair2[0]])
                        flag = True
                if pair1[0] == pair2[1]:
                    if [pair1[1], pair2[0]] not in (pairs + additional_pairs):
                        additional_pairs.append([pair1[1], pair2[0]])
                        flag = True
                if pair1[1] == pair2[0]:
                    if [pair1[0], pair2[1]] not in (pairs + additional_pairs):
                        additional_pairs.append([pair1[0], pair2[1]])
                        flag = True

    pairs += additional_pairs
    # print(pairs)

pairs = [[x, y] for x, y in pairs if x != y]

flag = True
while flag:
    flag = False
    for x1, x2 in pairs:
        if p[x1] == p0[x2] or p[x2] == p0[x1]:
            p[x2], p[x1] = p[x1], p[x2]
            flag = True

# print(p)
print(sum([1 for x, y in zip(p0, p) if x == y]))