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:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N
    for i, p in enumerate(P):
        F[p - 1] = i

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue

        if i == F[i]:
            res += 1
            continue

        S_num = {i}
        S_index = {F[i]}

        for j in range(i + 1, N):
            if already[j]:
                continue

            if U.is_pare(i, j):
                S_num.add(j)
                S_index.add(F[j])
                already[j] = True
        res += len(S_num & S_index)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N
    for i, p in enumerate(P):
        F[p - 1] = i

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue

        S_num = {i}
        S_index = {F[i]}
        for j in range(i + 1, N):
            if already[j]:
                continue

            if U.is_pare(i, j):
                S_num.add(j)
                S_index.add(F[j])
                already[j] = True
        res += len(S_num & S_index)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x):
        #要素xの根の番号を返す
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく(付け替える)
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
    def size(self, x):
        #要素xの所属するグループの頂点数を調べる
        #根のparentにサイズが格納されている
        return -self.parent[self.root(x)]
    def merge(self, x, y):
        #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        #大きい方(x)に小さい方(y)をくっつけたい
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))

p = list(map(int,input().split()))
UF = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    UF.merge(x-1,y-1)

ans = 0
L = [i for i in range(N) if UF.root(i)==i]
for i in range(len(L)):
    if UF.size(L[i])==1:
        if L[i]==p[L[i]]-1:
            ans +=1
    else:
        S = UF.family(L[i])
        T = [p[i]-1 for i in S]
        ans += len(set(S).intersection(set(T)))
print(ans)

Submission status: Time Limit Exceeded

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

class UnionFind:
    def __init__(self, n):
        #ノード数nの配列を作る
        #親の番号を格納する
        #-> 自分が根だった場合は、-(その集合のサイズ)とする
        #作るときはparentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent = [-1 for _ in range(n)]
        self.n = n
    def root(self, x):
        #要素xの根の番号を返す
        if self.parent[x] < 0:
            # 自分が根
            return x
        # 要素xの親を要素xの根に変えておく(付け替える)
        # 次の呼び出しが早くなる
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]
    def size(self, x):
        #要素xの所属するグループの頂点数を調べる
        #根のparentにサイズが格納されている
        return -self.parent[self.root(x)]
    def merge(self, x, y):
        #xとyを結合する
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        #大きい方(x)に小さい方(y)をくっつけたい
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
    def family(self,x): # xが属する連結集合を返す
        return [i for i in range(self.n) if self.issame(i,x)]
    def maximum(self): # 連結最大集合を返す
        return self.family(self.parent.index(min(self.parent)))

p = list(map(int,input().split()))
UF = UnionFind(N)
for i in range(M):
    x,y = map(int,input().split())
    UF.merge(x-1,y-1)

ans = 0
L = [i for i in range(N) if UF.root(i)==i]
for i in range(len(L)):
    S = UF.family(L[i])
    T = [p[i]-1 for i in S]
    ans += len(set(S).intersection(set(T)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    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) 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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
P = LIST()
L = [LIST() for i in range(M)]

dic = defaultdict(list)
tree = UnionFind(N+1)
for a, b in L:
    tree.union(a, b)

a = tree.all_group_members()

ans = 0
for i in range(1, N+1):
    if tree.find(i) == tree.find(P[i-1]):
        ans += 1
print(ans)
# print(a)
# for key, l in a.items():
#     for y in l:
#         dic[key].append(P[y-1])

# print(a)
# youso_set = set()
# graph_set = set()
# ans = 0
# for key, l in a.items():
#     if key == 0:
#         continue
#     youso_set = set(dic[key])
#     graph_set = set(l)
#     intersec = len(youso_set & graph_set)
#     ans += intersec
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    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) 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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
P = LIST()
L = [LIST() for i in range(M)]

dic = defaultdict(list)
tree = UnionFind(N+1)
for a, b in L:
    tree.union(a, b)

a = tree.all_group_members()
# print(a)
for key, l in a.items():
    for y in l:
        dic[key].append(P[y-1])

youso_set = set()
graph_set = set()

ans = 0

for key, l in a.items():
    if key == 0:
        continue
    youso_set = set(dic[key])
    graph_set = set(l)
    intersec = len(youso_set & graph_set)
    ans += intersec
print(ans)

Submission status: Time Limit Exceeded

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

ll=[i for i in range(1,n+1)]
lr=[1 for i in range(n)] #木のランク用

for i in range(m):
    a=max(l[i][0],l[i][1])
    b=min(l[i][0],l[i][1])
    lll=[a,b]
    while ll[a-1]!=a:
        a=ll[a-1]
        lll.append(a)
    while ll[b-1]!=b:
        b=ll[b-1]
        lll.append(b) #a,bの根を探索する
    
    if a!=b: #根が同じならそのまま
        if lr[a-1]==lr[b-1]:
            ll[b-1]=a
            lr[a-1]+=1
        elif lr[a-1]>lr[b-1]:
            ll[b-1]=a
        elif lr[a-1]<lr[b-1]:
            ll[a-1]=b
        for j in lll:
            ll[j-1]=a
k=0
for i in range(n):
    a=p.index(i+1)+1
    lll=[a]
    while ll[a-1]!=a:
        a=ll[a-1]
        lll.append(a)
    for j in lll:
        ll[j-1]=a
    b=i+1
    lll=[b]
    while ll[b-1]!=b:
        b=ll[b-1]
        lll.append(b)
    for j in lll:
        ll[j-1]=b
    if a==b:
        k+=1
        

print(k)

Submission status: Time Limit Exceeded

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

ll=[i for i in range(1,n+1)]

def root(a,l):
    while l[a-1]!=a:
        a=l[a-1]
    return a

for i in range(m):
    a=max(l[i][0],l[i][1])
    b=min(l[i][0],l[i][1])
    lll=[]
    while ll[a-1]!=a:
        a=ll[a-1]
        lll.append(a)
    for j in lll:
        ll[j-1]=a
    lll=[]
    while ll[b-1]!=b:
        b=ll[b-1]
        lll.append(b) #a,bの根を探索し、ついでに経路上のを根へつなぎなおす
    for j in lll:
        ll[j-1]=b
    if a!=b: #根が同じならそのまま
        ll[b-1]=a
k=0
for i in range(n):
    if root(p.index(i+1)+1,ll)==root(i+1,ll):
        k+=1

print(k)

Submission status: Time Limit Exceeded

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

ll=[i for i in range(1,n+1)]

def root(a,l):
    while l[a-1]!=a:
        a=l[a-1]
    return a

for i in range(m):
    a=max(l[i][0],l[i][1])
    b=min(l[i][0],l[i][1])
    a=root(a,ll) 
    b=root(b,ll) #a,bの根を探索

    if a!=b: #根が同じならそのまま
        ll[b-1]=a

m=0
for i in range(n):
    if root(p.index(i+1)+1,ll)==root(i+1,ll):
        m+=1

print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
                    indlist.add(p.index(k))
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for num,ind in xy[j]:
                if not alr[num]:
                    alr[num] = True
                    stack.append(num)
                    numlist.add(num)
                    indlist.add(ind)
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0
for i in range(N):
    if alr[i] and p[i] == i:
        count += 1
i = 0
while True:
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    if False in alr:
        i = alr.index(False)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0
for i in range(N):
    if alr[i] and p[i] == i:
        count += 1
i = 0
while True:
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
    if False in alr:
        i = alr.index(False)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0
for i in range(N):
    if alr[i] and p[i] == i:
        count += 1
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
print(count)

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

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

print(sum(len(set(mem)&set(P[i] for i in mem)) for _, mem in UF.all_group_members().items()))

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())
pl = list(map(int,input().split()))
uf = UnionFind(n)
for _ in range(m):
   x,y = map(int,input().split())
   uf.union(x-1,y-1)
ans = 0
for member in uf.all_group_members().values():
   a = [pl[i]-1 for i in member]
   ans += len(set(a) & set(member))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#97d
N,M = map(int, input().split())
p_list = [0] + [int(e) for e in input().split()]

#間で接続があれば遠隔で入れ替えできるので、まずは接続しているグループにまとめる。
number_group_dict = dict()
group_number_dict = dict()
new_group_number = 0
xy_set = set()

for i in range(M): #10**5
    x,y = map(int, input().split())
    if x > y:
        x,y = y,x
    if (x,y) not in xy_set:
        xy_set.add((x,y))
      
xy_list = list(xy_set)
xy_list.sort(reverse = True)
    
for xy in xy_list: #10**5
    x = xy[0]
    y = xy[1]
    is_x_in_ngd = x in number_group_dict #in dictはO(1)
    is_y_in_ngd = y in number_group_dict
    
    if is_x_in_ngd is False and is_y_in_ngd is False:
        group_number_dict[new_group_number] = set([x,y])
        number_group_dict[x] = new_group_number
        number_group_dict[y] = new_group_number
        new_group_number += 1
    else:
        if is_x_in_ngd is True and is_y_in_ngd is True:
            group_number_a = number_group_dict[x]
            group_number_b = number_group_dict[y]
            if group_number_a != group_number_b:
                group_number_dict[group_number_a].update(group_number_dict[group_number_b]) #group_number_dict[group_number_a] = group_number_dict[group_number_a] | group_number_dict[group_number_b]
                for number in group_number_dict[group_number_b]:
                    number_group_dict[number] = group_number_a
                del group_number_dict[group_number_b]
        elif is_x_in_ngd is True:
            group_number = number_group_dict[x]
            group_number_dict[group_number].add(y)
            number_group_dict[y] = group_number
        elif is_y_in_ngd is True:
            group_number = number_group_dict[y]
            group_number_dict[group_number].add(x)
            number_group_dict[x] = group_number

ans = 0

for i in range(1,N+1): #10**5
    if p_list[i] == i:
        ans += 1
    elif p_list[i] in number_group_dict:
        group_number = number_group_dict[p_list[i]]
        if i in group_number_dict[group_number]:
            ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#97d
N,M = map(int, input().split())
p_list = [0] + [int(e) for e in input().split()]

#間で接続があれば遠隔で入れ替えできるので、まずは接続しているグループにまとめる。
number_group_dict = dict()
group_number_dict = dict()
new_group_number = 0

for i in range(M): #10**5
    x,y = map(int, input().split())
    
    is_x_in_ngd = x in number_group_dict #in dictはO(1)
    is_y_in_ngd = y in number_group_dict
    
    if is_x_in_ngd is False and is_y_in_ngd is False:
        group_number_dict[new_group_number] = set([x,y])
        number_group_dict[x] = new_group_number
        number_group_dict[y] = new_group_number
        new_group_number += 1
    else:
        if is_x_in_ngd is True and is_y_in_ngd is True:
            group_number_a = number_group_dict[x]
            group_number_b = number_group_dict[y]
            if group_number_a != group_number_b:
                group_number_dict[group_number_a].update(group_number_dict[group_number_b]) #group_number_dict[group_number_a] = group_number_dict[group_number_a] | group_number_dict[group_number_b]
                for number in group_number_dict[group_number_b]:
                    number_group_dict[number] = group_number_a
                del group_number_dict[group_number_b]
        elif is_x_in_ngd is True:
            group_number = number_group_dict[x]
            group_number_dict[group_number].add(y)
            number_group_dict[y] = group_number
        elif is_y_in_ngd is True:
            group_number = number_group_dict[y]
            group_number_dict[group_number].add(x)
            number_group_dict[x] = group_number
            
#print(group_number_dict)
#print(number_group_dict)

ans = 0

for i in range(1,N+1): #10**5
    if p_list[i] == i:
        ans += 1
    elif p_list[i] in number_group_dict:
        group_number = number_group_dict[p_list[i]]
        if i in group_number_dict[group_number]:
            ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def search(r):
    while root[r] != r: r = root[r]
    return r
        
def rebuild(r, n):
    while root[r] != r: root[r], r = n, root[r]
    
N, M = map(int, input().split())
p = list(map(int, input().split()))

root = {i:i for i in range(1, N+1)}
size = {i:1 for i in range(1, N+1)}

for i in range(M):
    x, y = map(int, input().split())
    x, y = p[x-1], p[y-1]
    
    x_r, y_r = search(x), search(y)
    if x_r == y_r: continue

    root[x_r] = y_r
    size[y_r] = max(size[y_r], size[x_r])
    
    if size[y_r] > 10:
        rebuild(x, y_r)
        rebuild(y, y_r)
        size[y_r] = 1
    
ans = 0

for i, j in enumerate(p):
    if search(i+1) == search(j): ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def search(r):
    while root[r] != r: r = root[r]
    return r
        
N, M = map(int, input().split())
p = list(map(int, input().split()))

root = {i:i for i in range(1, N+1)}
size = {i:1 for i in range(1, N+1)}

for i in range(M):
    x, y = map(int, input().split())
    x, y = p[x-1], p[y-1]
    
    x_r, y_r = search(x), search(y)
    if x_r == y_r: continue

    root[x_r] = y_r
    size[y_r] += size[x_r]
    
ans = 0

for i, j in enumerate(p):
    if search(i+1) == search(j): ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int,input().split())
ps = [0] + list(map(int,input().split()))

memo = [[] for _ in range(n+1)]
connect = [[] for _ in range(n+1)]
visited = [0]*(n+1)

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

for i in range(1,n+1):
    connect[i] = memo[i]
    que = deque(memo[i])
    while que:
        vtx = que.popleft()
        for num in memo[vtx]:
            if num not in connect[i]:
                que.append(num)
                connect[i].append(num)

for i in range(1,n+1):
    if ps[i] == i:
        continue
    else:
        pos = ps.index(i)
        if pos in connect[i]:
            ps[pos] = ps[i]
            ps[i] = i

cnt = 0
for i in range(1,n+1):
    if ps[i] != i:
        cnt += 1
print(n - cnt)