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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#UnionFindのクラス
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 set([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,ipt().split())
    p = [int(i)-1 for i in ipt().split()]
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,ipt().split())
        uf.union(x-1,y-1)

    ans = 0
    for i in uf.all_group_members().values():
        for j in i:
            if p[j] in i:
                ans += 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

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

d=[-1]*N

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

LN=[-1]*N
lis=[]
idx=0
for i in range(N):
    if LN[i]==-1:
        temp=members(i)
        l=[]
        for j in temp:
            LN[j]=idx
            l.append(p[j])
        lis.append(l)
        idx+=1

ans=0
for i in range(N):
    for j in lis[LN[i]]:
        if i+1==j:
            ans+=1
            lis[LN[i]].remove(i+1)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

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

d=[-1]*N

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

LN=[-1]*N
lis=[]
idx=0
for i in range(N):
    if LN[i]==-1:
        temp=members(i)
        lis.append(temp)
        for j in temp:
            LN[j]=idx
        idx+=1

ans=0
for i in range(N):
    for j in lis[LN[i]]:
        if i+1==p[j]:
            ans+=1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(6500)

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def members(n):
    p=find(n)
    ans=[]
    for i in range(N):
        if find(i)==p:
            ans.append(i)
    return ans

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

d=[-1]*N

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

ans=0
for i in range(N):
    lis=members(i)
    for j in lis:
        if i+1==p[j]:
            ans+=1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
n, m = map(int, readline().split())
P = list(map(lambda x:int(x)-1, readline().split()))
G = [set() for _ in range(n)]
for i in range(m):
    x, y = map(lambda x:int(x)-1, readline().split())
    G[x].add(y)
    G[y].add(x)

D = {}
cnt = 0
V = [-1]*n
while -1 in V:
    st = V.index(-1)
    que = deque([st])
    V[st] = cnt
    D[cnt] = set([P[st]])
    while que:
        nw = que.popleft()
        for nx in G[nw]:
            if V[nx] != -1: continue
            D[cnt].add(P[nx])
            V[nx] = cnt
            que.append(nx)
    cnt += 1
print(sum([int(i in D[V[i]]) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,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) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n,m=map(int,input().split())
p=list(map(int,input().split()))
tree=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  tree.union(x-1,y-1)
res=tree.all_member()
ans=0
for i in res:
  l=set(res[i])
  for j in l:
    if tree.same(p[j]-1,j):
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,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) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n,m=map(int,input().split())
p=list(map(int,input().split()))
tree=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  tree.union(x-1,y-1)
res=tree.all_member()
ans=0
for i in res:
  l=set(res[i])
  for j in l:
    if p[j]-1 in l:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,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) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

n,m=map(int,input().split())
p=list(map(int,input().split()))
tree=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  tree.union(x-1,y-1)
res=tree.all_member()
ans=0
for i in res:
  l=set(res[i])
  for j in l:
    if p[j]-1 in l:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


class UnionFind:
    # 初期化
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        # 親要素のノード番号を格納する.初めは全て親ノード.
        # self.parent[x] == x の時，そのノードは根.
        self.parent = [i for i in range(n_nodes)]
        # 木の高さを格納する．
        self.rank = [1] * n_nodes
        # 自分と同じグループの要素数を格納．親要素を参照するようにする
        self.size = [1] * n_nodes

    # 検索. 根を返す.
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 一度調べた値は，根に繋ぎ直す.
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    # 併合.
    # 木の高さが低くなるように.
    # 親要素の書き換えは少ない方がいい
    def unite(self, x, y):
        # 根を探す．
        x = self.find(x)
        y = self.find(y)
        # 根が同じ場合はそのまま
        if x == y:
            return
        # 木の高さを比較し，低い方を高い方の根に貼る.
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    # 同一グループに所属する要素数を返す
    def get_size(self, x):
        return self.size[self.find(x)]

    # 親要素のリストを返す
    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

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

    # 同じグループに所属する要素の集合を返す
    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    # 全ての根に対する，グループのメンバーを返す．
    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    UF = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        UF.unite(x - 1, y - 1)
    member = UF.get_members_dict()
    par = list(member.keys())
    cnt = 0
    for p in par:
        d = []
        for m in member[p]:
            d.append(P[m] - 1)
        mem = np.array(member[p])
        d = np.array(d)
        # print(mem)
        # print(d)
        cnt += len(np.intersect1d(mem, d))
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True

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

    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    par = [-1] * n
    for _ in range(m):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        unite(x, y)

    r = 0
    for i1 in range(n):
        ichi = p.index(i1 + 1)
        r += same(i1, ichi)
    print(r)


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()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
for root in union_find.roots():
    idx_set = set(union_find.members(root))
    ps_set = set([p[i]-1 for i in union_find.members(root)])
    res += len(idx_set-ps_set)
print(n-res)

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()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
for root in union_find.roots():
    include_map = {i: 1 for i in union_find.members(root)}
    for i in union_find.members(root):
        ps = p[i]
        ps -= 1
        if ps in include_map:
            include_map[ps] = 0
    res += sum(include_map.values())
print(n-res)

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()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
for root in union_find.roots():
    include_map = {i: 1 for i in union_find.members(root)}
    for i in union_find.members(root):
        ps = p[i]
        ps -= 1
        if ps in include_map:
            include_map[ps] = 0
    res += sum(include_map.values())
print(n-res)

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=list(map(int,input().split()))
uf=UnionFind(N+1)
p=list(map(int,input().split()))
for i in range(M):
    x,y=list(map(int,input().split()))
    uf.union(x,y)
count=0
for i in range(1,N+1):
    if p[i-1] in uf.members(i):count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    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 find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #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)
    for i in range(M):
        a,b = map(int,input().split())
        uf.union(a-1, b-1)

    agm = uf.all_group_members()
    ret = 0
    for x in agm:
        for i in agm[x]:
            if P[i]-1 in agm[x]:
                ret+=1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

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

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

res = 0
for i in range(N):
  if i+1 == p[i]:
    res += 1
  elif uf.parents[i+1] == uf.parents[p[i]]:
    res += 1
  elif uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

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

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

res = 0
for i in range(N):
  if uf.parents[i+1] == uf.parents[p[i]]:
    res += 1
  elif uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

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

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

res = 0
for i in range(N):
  if uf.parents[i+1] == uf.parents[p[i]]:
    res += 1
  elif uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return
    self.parents[p2] = p1

  def find(self, node):
    # if self.parents[node] == node:
    #   return node
    # else:
    #   return self.find(self.parents[node])
    while self.parents[node] != node:
      node = self.parents[node]
    return node

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

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

res = 0
for i in range(N):
  if uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [ i for i in range(N+1) ]

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)

    if p1 == p2:
      return

    self.parents[p2] = p1

  def find(self, node):
    if self.parents[node] == node:
      return node
    else:
      return self.find(self.parents[node])

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

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

res = 0
for i in range(N):
  if uf.find(i+1) == uf.find(p[i]):
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = map(int,input().split())
lis = list(map(int,input().split()))
path = [[] for i in range(n)]

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

gone = np.array([-1] * n)
numberindex = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        realnumber = np.array([0] * n)
        numberindex.add(i)
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber[lis[a]-1] = 1
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        for num in numberindex:
            if realnumber[num] == 1:
                ans += 1
        numberindex = set()
print(ans)

Submission status: Time Limit Exceeded

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

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

gone = [-1] * n
numberindex = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        realnumber = [0] * n
        numberindex.add(i)
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber[lis[a]-1] = 1
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        for num in numberindex:
            if realnumber[num] == 1:
                ans += 1
        numberindex = set()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
    sp[ry]=sp[rx]|sp[ry]
    sp[rx]={}
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
    sp[ry]=sp[rx]|sp[ry]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    if rank[rx]>rank[ry]:
      r[ry]=rx
      sp[rx]=sp[rx]|sp[ry]
    elif rank[rx]<rank[ry]:
      r[rx]=ry
      sp[ry]=sp[rx]|sp[ry]
    else:
      r[rx]=ry
      sp[ry]=sp[rx]|sp[ry]
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)