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())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

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

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

l=list()
for i in range(N):
	f=False	
	for j in l:
		if j[0]==find(i):
			j[1].add(i)
			f=True
			break
	if not f:
		l.append([find(i),set([i])])

c=0
for i in l:
	for j in i[1]:
		if e[j] in i[1]:
			c+=1

print(c)

Submission status: Time Limit Exceeded

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y: return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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]-1,y[i]-1)
    answer = 0

    for indexes in uf.all_group_members().values():
        a = set(p[index] for index in indexes)
        b = set(index+1 for index in indexes)
        
        answer += len(a&b)

    print(answer)


    return


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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N)
for i in range(M):
    a, b = map(int,input().split())
    uf.union(a-1,b-1)
A = list(uf.all_group_members().values())
a = len(A)
B =[[] for i in range(a)]
import bisect
ans = 0
for i in range(a):
    S = A[i]
    for j in range(len(S)):
        s = S[j]
        insert_index = bisect.bisect_left(B[i],P[s]-1)
        B[i].insert(insert_index,P[s]-1)
    for k in range(len(S)):
        s = S[k]
        n = bisect.bisect_left(B[i],s)
        if n < len(B[i]):
            if B[i][n] == s:
                ans += 1
        

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N)
for i in range(M):
    a, b = map(int,input().split())
    uf.union(a-1,b-1)
A = list(uf.all_group_members().values())
a = len(A)
B =[[] for i in range(a)]
import bisect
ans = 0
for i in range(a):
    S = A[i]
    for j in range(len(S)):
        s = S[j]
        insert_index = bisect.bisect_left(B[i],P[s]-1)
        B[i].insert(insert_index,P[s]-1)
    for k in range(len(S)):
        s = S[k]
        if B[i].count(s) == 1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = UnionFind(N+1)
    for i in range(M):
        x, y = map(int, input().split())
        uf.union(x, y)
    ans = 0
    for r in uf.roots():
        ms = uf.members(r)
        p = set()
        for m in ms:
            p.add(P[m-1])
#        print(p, ms)
        ans += len(p & set(ms))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# D - Equals

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))
xy = sys.stdin.readlines()

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Equals

from collections import deque

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Equals

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

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

ans = 0
for n in range(1,N+1):
    if uf.find(n,p[n-1]):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

sets = uf.get_sets()

ans = 0
for s in sets:
    for n in s:
        if uf.find(n,p[n-1]):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect
def binary_search(s,val):
    if val > s[-1]:
        return False
    if val < s[0]:
        return False
    ind = bisect.bisect_left(s,val)
    return val == s[ind]
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

sets = uf.get_sets()

ans = 0
for s in sets:
    for n in s:
        if binary_search(s,p[n-1]):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self,nodes):
        self.parents = {node : node for node in nodes}
    def root(self,x):
        if x == self.parents[x]:
            return x
        else:
            rt = self.root(self.parents[x])
            self.parents[x] = rt
            return rt
    def find(self,x,y):
        return self.root(x) == self.root(y)
    def union(self,x,y):
        self.parents[self.root(x)] = self.root(y)
    def get_sets(self):
        res = defaultdict(list)
        for node, parent in self.parents.items():
            res[self.root(node)].append(node)
        # return [*res.values()]
        return list(res.values())

N,M = map(int,input().split(' '))
p = list(map(int,input().split(' ')))

uf = UnionFind(range(1,N+1))

for i in [0]*M:
    x, y = map(int,input().split(' '))
    uf.union(x,y)

sets = uf.get_sets()

ans = 0
for s in sets:
    for n in s:
        if p[n-1] in s:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        from copy import copy
        x = self.find(x)
        y = self.find(y)
        self.new = copy(self)
        self.new[y] = x
        return self.new

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

uf = UnionFind(n)
for x, y in xyxy :
    uf = uf.union(x-1, y-1)
for i in range(n) :
    uf.find(i)

d = {}
for i, k in enumerate(uf) :
    if k not in d :
        d[k] = {i}
    else :
        d[k].add(i)

e = {}
for k, set0 in d.items():
    e[k] = set()
    for i in set0 :
        e[k].add(pp[i]-1)

ans = 0
for k in d.keys() :
    set0 = d[k]
    set1 = e[k]
    ans += len(set0&set1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
l=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*m]
s=[0]*n
i=1
for x in l:
    if s[x[0]]==s[x[1]]==0:
        s[x[0]]=i
        s[x[1]]=i
        i+=1
    elif s[x[0]]==s[x[1]]>0:
        pass
    elif s[x[0]]==0:
        s[x[0]]=s[x[1]]
    elif s[x[1]]==0:
        s[x[1]]=s[x[0]]
    else:
        t=s[x[1]]
        for j in range(n):
            if s[j]==t:s[j]=s[x[0]]
list=list(set(s))
ans=0
if 0 in list:
    for j in range(n):
        if s[j]==0 and p[j]==j:ans+=1
    list.remove(0)
for j in list:
    ans+=len(set([p[k] for k in range(n) if s[k]==j])&set([k for k in range(n) if s[k]==j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def find(x):
    while union[x] != x:
        x = union[x]
    return x

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

union = [i for i in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    a, b = find(x), find(y)
    if a != b:
        union[a] = b

ans = 0
for idx, n in enumerate(p):
    x, y = find(idx+1), find(n)
    if x == y:
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
*P, = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for x,y in XY:
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        di = d[i]
        for j in E[i]:
            if d[j]!=-1:continue
            d[j] = di+1
            q.append(j)
    return d

done = [False]*N
ans = 0
for i in range(N):
    if done[i]:continue
    d = dist_bfs(N,E,i)
    J = set(j for j in range(N) if d[j]>=0)
    PJ = set(P[j]-1 for j in J)
    ans += len(J & PJ)
    for j in J:
        done[j] = True
print(ans)

Submission status: Time Limit Exceeded

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

root = {i:i for i in range(1, N+1)}
find = {idx+1:{n} for idx, n in enumerate(p)}

ans = 0
for i in range(M):
    x_, y_ = list(map(int, input().split()))
    x, y = x_, y_

    while x != root[x]:
        x = root[x]

    while y != root[y]:
        y = root[y]

    if x != y:
        find[x] |= find[y]
        find[y] = None
        root[x_] = root[y_] = root[y] = x

for i in range(1, N+1):
    r = root[i]
    while r != root[r]:
        r = root[r]

    if i in find[r]:
        find[r].remove(i)
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10000000)
n,m = map(int,input().split())
p = list(map(int,input().split()))
xy = [list(map(int,input().split())) for _ in range(m)]

Graph = [[] for _ in range(n)]
for x,y in xy:
    Graph[x-1].append(y-1)
    Graph[y-1].append(x-1)

check = [False for _ in range(n)]
def dfs(g,start,c,goal):
    c[start] = True
    if start == goal:
        return True
    for u in g[start]:
        if c[u]:
            continue
        if dfs(g,u,c,goal):
            return True
ans = 0
for i in range(n):
    c = check.copy()
    if dfs(Graph,i,c,p.index(i+1)):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

idx_dict = dict()
keys = []
for i in range(n):
    idx = u.find(i + 1)
    if idx not in keys:
        idx_dict[idx] = [i]
        keys.append(idx)
    else:
        idx_dict[idx].append(i)

counter = 0
for k in keys:
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)

Submission status: Time Limit Exceeded

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

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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

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

counter = 0
for k in keys:
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)

Submission status: Time Limit Exceeded

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

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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


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

counter = 0
for k in idx_dict.keys():
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)

Submission status: Time Limit Exceeded

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

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

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

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

dic=dict()

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

dic=dict()

for i in range(N):
    if z[i][0] not in dic.keys():
        dic[z[i][0]]=[i]
    else:
        dic[z[i][0]].append(i)
        
list1=list(dic.values())
list2=[[] for _ in [0]*len(list1)]

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

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

Submission status: Time Limit Exceeded

Solution code:


def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind = data.index(i + 1)
    ind += 1
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def get_p(ind):
    global parent
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]

parent = []

def main():
    global parent

    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [i for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        a_parent = get_p(a)
        b_parent = get_p(b)

        if a_parent != b_parent:
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)


    ans = 0

    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int) == get_p(ind):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()