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()))

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 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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

res = 0
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)

for g in uf.all_group_members().values():
    e = []
    for i in g:
        e.append(P[i]-1)
    res += len(set(g) & set(e))

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    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 Union(self, x, y):
        #入力ノードの親を探索
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        #既に同じ木に所属する場合
        if (x==y):
            return 
        
        #異なる木に所属する場合 -> rnkから判断して合併する
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            #rnkが同じ(深さが同じ)場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    """木(非連結成分)の数を数える"""
    #全連結成分にするために必要な橋の本数は、cnt - 1
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]


n,m = map(int,input().split())
uf = UnionFind(n)
p = list(map(int,input().split()))
d = {}
for i in range(n):
    d[p[i]] = i+1
for i in range(m):
    x,y = map(int,input().split())
    uf.Union(x,y)
x = []
for i in range(1, n+1):
    x.append(uf.Members(i))

res = 0
for i in range(n):
    if d[i+1] in x[i]:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    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 Union(self, x, y):
        #入力ノードの親を探索
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        #既に同じ木に所属する場合
        if (x==y):
            return 
        
        #異なる木に所属する場合 -> rnkから判断して合併する
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            #rnkが同じ(深さが同じ)場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    """木(非連結成分)の数を数える"""
    #全連結成分にするために必要な橋の本数は、cnt - 1
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]


n,m = map(int,input().split())
uf = UnionFind(n)
p = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    uf.Union(x,y)
x = []
for i in range(1, n+1):
    tmp = []
    for num in uf.Members(i):
        tmp.append(p[num-1])
    x.append(tmp)

res = 0
for i in range(n):
    if i+1 in x[i]:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
"""
#N,K,Mが入力
    n,k,m=LI() 
    #N
    #x1 y1
    #.  .
    #xn ynが入力
    N=I()
    p=LIR(N)
    print(n,k,m,p)
"""
############################## ユニオン木(union tree) ###################################
#uf=UnionFind(n)と使う
# print(uf.roots())
# print(uf.all_group_members())
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.par = [-1 for i in range(self.n+1)]
        self.rank = [0 for i in range(self.n+1)]#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。
    
    # 検索
    def find(self, x):
        # if self.par[x] == x:
        if self.par[x] <0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n+1) if self.find(i) == root]

    #すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.par) if x<0]

    #グループの数を返す
    def group_count(self):
        return len(self.roots())

    #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {int(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 resolve():
    n,m=LI()
    p=LI()
    x=LIR(m)

    uf=UnionFind(n)
    for i in range(m):
        uf.union(x[i][0],x[i][1])
    # print(uf.all_group_members())

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

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 2
5 3 1 4 2
1 3
5 4"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 2
3 2 1
1 2
2 3"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """8"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """5 1
1 2 3 4 5
1 5"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

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())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.union(a, b)
  
cnt = 0
G = uf.all_group_members()
for i,w in enumerate(List):
  if uf.find(i+1) == uf.find(w):
    cnt += 1
  
print(cnt)

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())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.union(a, b)
  
cnt = 0
G = uf.all_group_members()
for i in range(N):
  a = uf.find(List[i])
  b = G[a]
  if i+1 in b:
    cnt += 1
  
print(cnt)

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())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.union(a, b)
  
cnt = 0
for i in range(N):
  a = uf.find(List[i])
  b = uf.all_group_members()[a]
  if i+1 in b:
    cnt += 1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(M)]
table = []
table2 = set()
ans = 0
for i, x in enumerate(p):
    if i+1 == x:
        ans += 1
    else:
        table2.add(x)
id = 0
for x, y in xy:
    a, b = -1, -1
    for z in range(len(table)):
        if x in table[z]:
            a = z
            break
    for z in range(len(table)):
        if y in table[z]:
            b = z
            break
    if a == b:
        if a == -1:
            table.append({x, y})
    elif a == -1 or b == -1:
        if a == -1:
            table[b].add(x)
        else:
            table[a].add(y)
    else:
        table[a] |= table[b]
        table[b], table[-1] = table[-1], table[b]
        table.pop()


for x in range(len(table)):
    tmp = set()
    for a in table[x]:
        tmp.add(p[a-1])
    ans += len(table2 & table[x] & tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))

xy = [tuple(map(int, input().split())) for i in range(M)]

table = collections.defaultdict(set)

table2 = collections.defaultdict(int)
ans = 0
for i, x in enumerate(p):
    if i+1 == x:
        ans += 1
    else:
        table2[i + 1] = x
id = 0
for x, y in xy:
    a, b = -1, -1
    for z in table:
        if x in table[z]:
            a = z
            break
    for z in table:
        if y in table[z]:
            b = z
            break
    if a == b:
        if a == -1:
            table[id].add(x)
            table[id].add(y)
            id += 1
    elif a == -1 or b == -1:
        if a == -1:
            table[b].add(x)
        else:
            table[a].add(y)
    else:
        table[a] |= (table[b])
        del(table[b])

for x in table:
    for a in table[x]:
        if a in table2 and table2[a] in table[x]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

xy = [tuple(map(int, input().split())) for i in range(M)]

table = collections.defaultdict(set)

table2 = collections.defaultdict(int)
ans = 0
for i, x in enumerate(p):
    if i+1 == x:
        ans += 1
    else:
        table2[i + 1] = x
id = 0
for x, y in xy:
    a, b = -1, -1
    for z in table:
        if x in table[z]:
            a = z
            break
    for z in table:
        if y in table[z]:
            b = z
            break
    if a == b:
        if a == -1:
            table[id].add(x)
            table[id].add(y)
            id += 1
    elif a == -1 or b == -1:
        if a == -1:
            table[b].add(x)
        else:
            table[a].add(y)
    else:
        table[a] |= (table[b])
        del(table[b])

for x in table:
    for a in table[x]:
        if a in table2 and table2[a] in table[x]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        stack.append(i)
    while stack:     
        x = stack.pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
        
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        flg = True
        cnt += 1
        stack.append(i)
        connect = []
    while stack:     
        x = stack.pop()
        visited[x] = 1
        connect.append(x)
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
    if flg:
        for i in connect:
            conlist[i] = cnt
        flg = False
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        flg = True
        cnt += 1
        stack.append(i)
        connect = []
    while stack:     
        x = stack.pop()
        visited[x] = 1
        connect.append(x)
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
    if flg:
        for i in connect:
            conlist[i] = cnt
        flg = False
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        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(lambda x : int(x)-1,input().split()))
count = 0
uf = UnionFind(N)
for _ in range(M):
    i,j = map(lambda x : int(x)-1,input().split())
    uf.union(i,j)
dic = uf.all_group_members()
for i in range(N):
    if uf.same(p[i],i):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(si, ei):
  q = deque()
  q.append(si)
  used = set([])
  while len(q) > 0:
    prvi = q.pop()
    for i in g[prvi]:
      if i in used: continue
      if i == ei: return True
      q.append(i)
      used.add(i)
  return False

N,M = map(int,input().split())
P = [val-1 for val in map(int,input().split())]
g = {i:[] for i in range(N)}
ans = 0
for _ in range(M):
  x,y = map(int,input().split())
  g[x-1].append(y-1)
  g[y-1].append(x-1)

for i in range(N):
  if i == P[i]: ans += 1
  elif bfs(i,P[i]): ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush,heappop
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,m = (int(i) for i in input().split())
  p = list(int(i) for i in input().split())

  uf = UnionFind(n)
  for i in range(m):
    x,y = (int(i) for i in input().split())
    uf.union(x-1,y-1)
  groupnumber = uf.group_count()
  ans = 0
  for key,value in uf.all_group_members().items():
    tmp = []
    for val in value:
      heappush(tmp,p[val]-1)
      heappush(tmp,val)
    now = -1
    while tmp:
      next = heappop(tmp)
      if next == now:
        ans += 1
      now = next
  print(ans)

    
solve()

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 solve():
  n,m = (int(i) for i in input().split())
  p = list(int(i) for i in input().split())

  uf = UnionFind(n)
  for i in range(m):
    x,y = (int(i) for i in input().split())
    uf.union(x-1,y-1)
  groupnumber = uf.group_count()
  ans = 0
  for key,value in uf.all_group_members().items():
    tmp = []
    for val in value:
      tmp.append(p[val]-1)
      tmp.append(val)
    tmp = sorted(tmp)
    for i in range(len(tmp)-1):
      if tmp[i] == tmp[i+1]:
        ans += 1
  print(ans)

    
solve()

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 solve():
  n,m = (int(i) for i in input().split())
  p = list(int(i) for i in input().split())
  xy = []

  uf = UnionFind(n)
  for i in range(m):
    x,y = (int(i) for i in input().split())
    if x > y:
      x,y = y,x
    xy.append((x,y))
    uf.union(x-1,y-1)
  groupnumber = uf.group_count()
  ans = 0
  for key,value in uf.all_group_members().items():
    length = len(value)
    for i in range(length):
      val = p[value[i]]
      value.append(val-1)
    length = len(value)
    tmp = len(set(value))
    ans += length-tmp
  print(ans)

    
solve()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
P = list(map(lambda x: int(x)-1,input().split()))
tree = list(range(N))

def root(n):
    while True:
        if tree[n] == n:
            return n
        n = tree[n]

for i in range(M):
    x,y = map(lambda x: int(x)-1,input().split())
    rx = root(x)
    ry = root(y)
    if rx == ry:
        continue
    tree[rx] = ry

print(sum(map(lambda x: root(x)==root(P[x]),range(N))))

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 i in range(1, N+1):
    root = U.Find_Root(i)
    if p[i-1] in root_dict[root]:
      ans += 1
  print(ans)


if __name__ == "__main__":
  main()