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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
 
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[y] = x
        else:
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def main():
  N, M = map(int, input().split())
  p = list(map(int, input().split()))
  xy = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N+1)
  for x, y in xy:
    U.Unite(x, y)
  root_dict = {}
  for i in range(1, N+1):
    root = U.Find_Root(i)
    if root in root_dict:
      root_dict[root] += [i]
    else:
      root_dict[root] = [i]
  ans = 0
  for idx_list in root_dict.values():
    for idx in idx_list:
      if p[idx-1] in idx_list:
        ans += 1
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = []
for i in range(M):
  XY.append(list(map(int,input().split())))
#print(XY)

E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)
#print(E)

def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1
#print(visited)

G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)
#print(G)

ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(lambda x: int(x)-1, input().split()))
    parent = [k for k in range(N)]

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

    def unite(x,y):
        parent[find(x)] = find(y)

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

    ans = 0
    for k in range(N):
        if find(k) == find(p[k]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(int,input().split()))
    p = [p[k]-1 for k in range(N)]
    parent = [k for k in range(N)]

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

    def unite(x,y):
        parent[find(x)] = find(y)

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

    ans = 0
    for k in range(N):
        if find(k) == find(p[k]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(int,input().split()))
    p = [p[k]-1 for k in range(N)]
    parent = [k for k in range(N)]

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

    def unite(x,y):
        if find(x) != find(y):
            parent[find(x)] = find(y)

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

    ans = 0
    for k in range(N):
        if find(k) == find(p[k]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

G = [[] for i in range(N)]

for i in range(len(L)) :
    u,v = L[i]
    u -= 1
    v -= 1
    
    G[u].append(v)
    G[v].append(u)

explored = [0 for i in range(N)]

ans = 0

for i in range(N) :
    
    if explored[i] :
        continue
    
    explored[i] = 1
    q = deque([i])
    
    A = []
    B = []
    while q :
        now = q.popleft()
        
        A.append(now)
        B.append(P[now]-1)
        
        for to in G[now] :
            if explored[to] :
                continue
            
            q.append(to)
            explored[to] = 1
    
    for a in A :
        if a in B :
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [list() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].append(y)
  d[y].append(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [set() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].add(y)
  d[y].add(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
a = []
v = []

for i in range(n):
    if i not in v:
        connect.append([i])
        a.append([p[i]-1])
        v.append(i)
        stack =[i]
        visited = [i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if l[q][j] not in visited:
                    connect[-1].append(l[q][j])
                    a[-1].append(p[l[q][j]]-1)
                    visited.append(l[q][j])
                    stack.append(l[q][j])
                    v.append(l[q][j])

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)

Submission status: Time Limit Exceeded

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
v = []

for i in range(n):
    if i not in v:
        connect.append([i])
        v.append(i)
        stack =[i]
        visited = [i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if l[q][j] not in visited:
                    connect[-1].append(l[q][j])
                    visited.append(l[q][j])
                    stack.append(l[q][j])
                    v.append(l[q][j])

a = []
for i in range(len(connect)):
    a.append([])
    for j in connect[i]:
        a[-1].append(p[j]-1)

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)

Submission status: Time Limit Exceeded

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

l = [[0 for i in range(n)] for j in range(n)]

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

connect = []
v = []

for i in range(n):
    if i not in v:
        connect.append([i])
        v.append(i)
        stack =[i]
        visited = [i]
        while stack:
            q = stack.pop()
            for j in range(n):
                if l[q][j]==1 and j not in visited:
                    connect[-1].append(j)
                    visited.append(j)
                    stack.append(j)
                    v.append(j)

a = []
for i in range(len(connect)):
    a.append([])
    for j in connect[i]:
        a[-1].append(p[j]-1)

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        while self.parent[i] != i:
            i = self.parent[i]
        return i
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
ps = list(map(int, input().split()))
ps = [i-1 for i in ps]
swap =[list(map(int, input().split())) for i in range(M)]
u = UnionFind(N)
for x, y in swap:
    u.union(x-1, y-1)
ans = 0
for i, p in enumerate(ps):
    if u.find(i, p):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def find(self, i):
        while self.parent[i] != i:
            i = self.parent[i]
        return i
 
    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        self.parent[j] = i
N, M = map(int, input().split())
ps = list(map(int, input().split()))
ps = [i-1 for i in ps]
swap =[list(map(int, input().split())) for i in range(M)]
u = UnionFind(N)
for x, y in swap:
    u.union(x-1, y-1)
for i in range(N):
    u.parent[i] = u.find(i)
a = {}
for i, k in enumerate(u.parent):
    if k in a:
        a[k].append(i)
    else:
        a[k] = [i]
ans = 0
for i, p in enumerate(ps):
    for l in a.values():
        if i in l and p in l:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
p=[set()]+[set([int(x)]) for x in input().split()]
xy=[list(map(int, input().split())) for _ in range(M)]

for _ in range(10):
	for x,y in xy:
		p[x]=p[y]=p[x]|p[y]

print(sum([1 if i in s else 0 for (i, s) in enumerate(p)]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

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 

def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(x[i], y[i])

    rootl = [i for i in range(1,N+1) if uf.par[i] < 0]

    ans = 0
    for i in rootl:
        # そえじちゅーしゅつ
        tl = {j for j in range(1,N+1) if uf.same_check(i,j)} 
        # なかみちぇっく
        il = {p[j-1] for j in tl}
        # たしあわせ
        ans += len(tl & il)

    print(ans)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    p = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    x = [int()] * (M)  # type: "List[int]" 
    y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, p, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra

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

A = [[float("inf") for i in range(N)] for i in range(N)]
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

dist = dijkstra(A)
ans = N
for i in range(N) :
    if i == L[i] :
        continue
    if dist[i][L[i]] < float("inf") :
        continue    
    else :
        ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-


class UnionFind:
    '''
    配列を用いたUnionFind
    '''

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        '''
        xのグループ番号を返す
        '''
        return self.table[x]

    def union(self, x, y):
        '''
        xとyが同じグループならFalse
        xとyが違うグループなら、同じグループにする(くっつける)
        '''
        x1 = self.find(x)
        y1 = self.find(y)

        if x1 == y1:
            return False

        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True

    def same(self, x, y):
        '''
        xとyが同じグループならtrue
        '''
        x1 = self.find(x)
        y1 = self.find(y)
        return x1 == y1


N, M = map(int, input().split())
Un = UnionFind(N+1)
A = list(map(int, input().split()))

for _ in range(M):
    a, b = map(int, input().split())
    Un.union(a, b)

ans = 0
for i in range(N):
    if Un.same(A[i], i+1):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


class UnionFind:
    def __init__(self, size):
        self.table = list(range(size))

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1:
            return False
        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x - 1, y - 1)
print(sum([uf.find(i) == uf.find(p - 1) for i, p in enumerate(ps)]))

Submission status: Time Limit Exceeded

Solution code:
import sys

def add_x2y(x, y, d, key2rep):
    rep = key2rep[y]
    big_rep = key2rep[x]
    if rep == big_rep:
        return
    for old in d[big_rep]:
        d[rep].add(old)
        key2rep[old] = rep

N, M = map(int,input().split(' '))
p_list = [int(i) for i in input().split(' ')]
d = {i+1:set([i+1]) for i in range(N)}
key2rep = {i+1:i+1 for i in range(N)}

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), d, key2rep)

print(len([1 for i in range(N) if p_list[i] in d[key2rep[i+1]]]))

Submission status: Time Limit Exceeded

Solution code:
import sys

def create_dict(N):
    d = {}
    key2rep = {}
    for i in range(N):
        d[i+1] = set([i+1])
        key2rep[i+1] = i+1
    return d, key2rep

def key2rep_iter(x, key2rep):
    if key2rep[x] != x:
        return key2rep_iter(key2rep[x], key2rep)
    return key2rep[x]

def add_x2y(x, y, d, key2rep):
    rep = key2rep_iter(y, key2rep)
    big_rep = key2rep_iter(x, key2rep)
    if rep == big_rep:
        return
    d[rep] = d[rep] | d[big_rep]
    key2rep[big_rep] = rep
    d[big_rep] = set()
#    print(d)

N, M = map(int,input().split(' '))
d, key2rep = create_dict(N)
p_list = list(map(int,input().split(' ')))

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), d, key2rep)

score = 0
for i in d:
    for x in d[i]:
        if p_list[x-1] in d[i]:
            score += 1
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys

def create_dict(N):
    d = {}
    key2rep = {}
    for i in range(N):
        d[i+1] = set([i+1])
        key2rep[i+1] = i+1
    return d, key2rep

def add_x2y(x, y, d, key2rep):
    rep = key2rep[y]
    big_rep = key2rep[x]
    if rep == big_rep:
        return
    for old in d[big_rep]:
        d[rep].add(old)
        key2rep[old] = rep
    d[big_rep] = set()
#    print(d)

N, M = map(int,input().split(' '))
d, key2rep = create_dict(N)
p_list = list(map(int,input().split(' ')))

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), d, key2rep)

score = 0
for i in d:
    for x in d[i]:
        if p_list[x-1] in d[i]:
            score += 1
print(score)

Submission status: Time Limit Exceeded

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

set_list = []
edge = [[] for _ in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x, y = x-1, y-1

    s1 = None
    s2 = None
    for i, se in enumerate(set_list):
        if x in se:
            s1 = se
            xi = i
        if y in se:
            s2 = se
            yi = i

    if s1 == None:
        if s2 == None:
            set_list.append({x, y})
        else:
            s2.add(x)
    else:
        if s2 == None:
            s1.add(y)
        elif s1 == s2:
            continue
        else:
            s = s1 | s2
            set_list.append(s)
            l = [xi, yi]
            l.sort()
            xi, yi = l
            del set_list[yi]
            del set_list[xi]

count = 0
for i in range(N):
    if p[i] == i+1:
        count += 1
    else:
        for se in set_list:
            if {i, p[i]-1} <= se:
                count += 1
                continue

print(count)

Submission status: Time Limit Exceeded

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

set_list = []
edge = [[] for _ in range(N)]
for i in range(M):
    x, y = list(map(int, input().split()))
    x, y = x-1, y-1

    s1 = None
    s2 = None
    for i, se in enumerate(set_list):
        if x in se:
            s1 = se
        if y in se:
            s2 = se

    if s1 == None:
        if s2 == None:
            set_list.append({x, y})
        else:
            s2.add(x)
    else:
        if s2 == None:
            s1.add(y)
        elif s1 == s2:
            continue
        else:
            s = s1 | s2
            set_list.append(s)
            set_list.remove(s1)
            set_list.remove(s2)
count = 0
for i in range(N):
    if p[i] == i+1:
        count += 1
    else:
        for se in set_list:
            if {i, p[i]-1} <= se:
                count += 1
                continue

print(count)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

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):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

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):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

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[:]
loop = True
while loop:
    loop = False
    LSET2 = []
    i = 0
    while i < len(LSET):
        j = i + 1
        tmp = LSET[i]
        if not tmp:
            i += 1
            continue
        while j < len(LSET):
            if  LSET[j] and not tmp.isdisjoint(LSET[j]):
                tmp |= LSET[j]
                loop = True
                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])
print(result)

Submission status: Time Limit Exceeded

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[:]
loop = True
while loop:
    loop = False
    LSET2 = []
    i = 0
    while i < len(LSET):
        j = i + 1
        tmp = LSET[i]
        if not tmp:
            i += 1
            continue
        while j < len(LSET):
            if  LSET[j] and not tmp.isdisjoint(LSET[j]):
                tmp |= LSET[j]
                loop = True
                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]])
PSET = [{P[i-1] for i in s}for s in LSET]
result += sum([len(l&p) for l,p in zip(LSET,PSET)])
print(result)

Submission status: Time Limit Exceeded

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[:]
loop = True
while loop:
    loop = False
    LSET2 = []
    i = 0
    while i < len(LSET):
        j = i + 1
        tmp = LSET[i]
        if not tmp:
            i += 1
            continue
        while j < len(LSET):
            if  LSET[j] and not LSET[i].isdisjoint(LSET[j]):
                tmp |= LSET[j]
                loop = True
                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]])
PSET = [{P[i-1] for i in s}for s in LSET]
LPSET = [l&p for l,p in zip(LSET,PSET)]
result += sum([len(i)for i in LPSET])
print(result)

Submission status: Time Limit Exceeded

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

x = []
for i in range(m):
    x.append(list(map(int, input().split(" "))))

tree = []
for i in x:
    a = []
    for t in range(len(tree)):
        temp = i + tree[t]
        if len(temp) > len(set(temp)):
            a.append(t)
            if len(a) >= 2:
                break
    if len(a) == 0:
        tree.append(i)
    elif len(a) == 1:
        tree[a[0]] = list(set(tree[a[0]] + i))
    elif len(a) == 2:
        tree[a[0]] = list(set(tree[a[0]] + tree[a[1]]))
        del tree[a[1]]

result = 0
for t in tree:
    temp = []
    for i in t:
        temp.append(p[i - 1])
        p[i - 1] = 0
    temp = temp + t
    result += len(temp) - len(set(temp))

for i in range(n):
    if p[i] == i + 1:
        result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = list(map(int, input().split()))
S = []

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

    for t in S[:]:
        if t & s:
            S.remove(t)
            s = s|t

    S.append(s)


count = 0

for i in range(N):
    if P[i] == i + 1:
        count += 1
    else:
        for s in S:
            if i+1 in s and P[i] in s:
                count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = list(map(int, input().split()))
S = []

for j in range(M):
    x, y = map(int, input().split())
    s = {x, y}
    S.append(s)


count = 0

for i in range(N):
    if P[i] == i + 1:
        count += 1
    else:
        T = {i+1}
        U = set()
        while T - U and not P[i] in T:
            U = T
            for s in S:
                if T & s:
                    T = T|s
        if P[i] in T:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = list(map(int, input().split()))
S = []

for j in range(M):
    x, y = map(int, input().split())
    s = {x, y}
    S.append(s)


count = 0

for i in range(N):
    if P[i] == i + 1:
        count += 1
    else:
        T = {i+1}
        U = set()
        while T - U:
            U = T
            for s in S:
                if T & s:
                    T = T|s
        if P[i] in T:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**5
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
            if not pi in next_children:
                next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**(10)
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
            next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

Submission status: Time Limit Exceeded

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] = gn
        l[y-1] = gn
        g.append([x,y])
        gn += 1
    elif l[x-1] != -1 and l[y-1] != -1:
        if l[x-1] == l[y-1]:
            pass
        else:
            if l[x-1]<l[y-1]:
                tmp = g[l[y-1]]
                for z in g[l[y-1]]:
                    l[z-1] = l[x-1]
                g[l[x-1]] += tmp
            else:
                tmp = g[l[x-1]]
                for z in g[l[x-1]]:
                    l[z-1] = l[y-1]
                g[l[y-1]] += tmp 
    else:
        if l[x-1] == -1:
            l[x-1] = 0+l[y-1]
            g[l[y-1]].append(x)
        else:
            l[y-1] = 0+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)