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: Accepted

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


class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n # 親: -(属するノード数), それ以外: (親ノードindex)

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x]) # compression
            return self.nodes[x]

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, M: int, p: "List[int]", x: "List[int]", y: "List[int]"):
    U = UnionFind(2 * N + 1)
    for i, pi in enumerate(p):
        U.unite(i+1, N + pi)
    for xx, yy in zip(x, y):
        U.unite(xx, yy)
    res = 0
    for i in range(1, N+1):
        if U.has_same_root(i, N+i):
            res += 1
    
    print(res)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

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


def main():
    N, M = map(int,input().split())
    L = list(map(int,input().split()))
    UF = UnionFind(N)
    
    for i in range(M) :
        A, B = map(int,input().split())
        A -= 1
        B -= 1
        UF.union(A, B)
    
    ans = 0
    
    for i, v in enumerate(L) :
        ans += (UF.same_root(i, v-1))
    
    print(ans)
    
        

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

from collections import defaultdict
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups_num(self):
        if isinstance(self.parent,list):
            return len(list(filter(lambda x: x<0, self.parent)))
        else: # self.parent: defaultdict
            return len(list(filter(lambda x: x<0, self.parent.values())))

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, M = inpl()
p = inpl()
xy = [None]*M
for i in range(M):
    x, y = inpl()
    xy[i] = (x-1, y-1)

uf = UnionFind(2*N)
for i in range(N):
    uf.merge(i,(p[i]-1)+N)
for x, y in xy:
    uf.merge(x,y)
ans = 0
for i in range(N):
    if uf.connected(i,i+N):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
P = list(map(lambda x:int(x)-1,input().split()))

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

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

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

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


uf = UnionFind(n)

for i in range(m):
    x,y = map(lambda x:int(x) - 1,input().split())
    uf.unite(x,y)
    
ans = 0 
for i in range(n):
    if uf.find(i)==uf.find(P[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n, m = li()
p = list(li_())

uf = UnionFind(n)
for _ in range(m):
    x, y = li_()
    uf.unite(x, y)

for i in range(n):
    uf.find(i)

ans = 0
for i, pi in enumerate(p):
    if uf.isSame(i, pi):
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x
        
        self.par[y] = x
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def __repr__(self):
        return ', '.join(str(x) for x in self.par)

t = UnionFind(N)
for x, y in X:
    t.unite(x - 1, y - 1)
    
cnt = 0
for i in range(N):
    cnt += int(t.same(i, p[i] - 1))
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

n,m = list(map(int,input().split()))
p = list(map(lambda x: int(x)-1,input().split()))

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

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

print(ans)
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
P=list(map(int, input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N,P):
        self.Parent=[-1]*N
        self.num=[{p-1:1} for p in P]
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            self.num[rm].update(self.num[rn])
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N,P)
for xy in XY:
    u.unite(xy[0]-1,xy[1]-1)
ans=0
for n in range(N):
    if n in u.num[u.root(n)]:
        ans+=1
print(ans)

Submission status: Accepted

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


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[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            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 size(self, x):
        return -self.root[self.find_root(x)]


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

ans = 0
for i in range(N):
    if UF.isSameGroup(i+1, p[i]):
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

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

from collections import deque

def BFS(vi,color,color_list,e_list):
    Q = deque([vi])
    color_list[vi]=color
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=color
                Q.appendleft(v1)
    return color_list

color_list = [-1 for i in range(N)]
color = 0
for i in range(N):
    if color_list[i]==-1:
        color_list = BFS(i,color,color_list,e_list)
        color+=1
count=0

for i in range(N):
    if color_list[p[i]-1]==color_list[i]:
        count+=1

print(count)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)

N, M = map(int, input().split())
L = [int(v) - 1 for v in input().split()]

u = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    u.unite(x - 1, y - 1)
    
c = 0
for i in range(N):
    if u.same(i, L[i]):
        c += 1
    
print(c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

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.union(x-1, y-1)
ans = 0
for i in range(N):
    if uf.is_connected(i, P[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
P=[int(i) for i in input().split()]
PP=[0]*n
for i in range(n):
  PP[P[i]-1]=i+1
par=[-1]*n

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)

def size(x):
  return -par[find(x)]

for i in range(m):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(n):
  if same(i,PP[i]-1):
    ans+=1
print(ans)

Submission status: Accepted

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

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

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)

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

def union(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

for i in range(m):
    x, y = map(int, input().split())
    union(p[x - 1], p[y - 1])
ans = 0
for i in range(n):
    if same_check(i + 1, p[i]):
        ans += 1
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n)] #親
        self.rank = [1]*n #深さ
        self.size = [1]*n #size[i]:=iを根とするグループのサイズ
    
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                    
    def same(self,x,y):
        return self.find(x) == self.find(y)
        
    def group_size(self,x):
        return self.size[self.find(x)]

uf = UnionFind(N)
ans = 0
for x, y in xy:
    uf.unite(x,y)
for i in range(N):
    if uf.same(i,p[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()


N,M = na()
p = na()

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        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 Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        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が同じ（深さに差がない場合）は1増やす
            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)]
tr = UnionFind(N)
for i in range(M):
    q1,q2 = na()
    tr.Unite(q1,q2)
ans =0
for i in range(N):
    #p[i]がpの中でp[i]番目にある数字と同じグループにいたらOK
    tmp = p[p[i]-1]
    if(tr.isSameGroup(p[i],tmp)):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        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 Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        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が同じ（深さに差がない場合）は1増やす
            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)]


def solve():
    # N,M = map(int, input().split())
    N,M = map(int,input().split())
    # P = list(map(int(input().split())))
    P = list(map(int,input().split()))
    XY = []
    U = UnionFind(N+1)

    for x,y in [list(map(int,input().split())) for _ in range(M)]:
        U.Unite(x,y)

    ans = 0
    for e,p in enumerate(P,1):
        if U.isSameGroup(e,p):
            ans += 1
    print(ans)

    # XY= [ list(map(int(input().split()))) for _ in range(M)]


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import defaultdict
N,M=map(int,raw_input().split())
P=map(int,raw_input().split())
X=[];Y=[]
for i in range(M):
    x,y=map(int,raw_input().split())
    X.append(x);Y.append(y)

#### https://www.kumilog.net/entry/union-find#%E6%9C%80%E7%B5%82%E7%9A%84%E3%81%AA%E3%82%B3%E3%83%BC%E3%83%89
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
######################################################################################################
uf=UnionFind(N+1)
for x,y in zip(X,Y):
    uf.union(x,y)
groups=defaultdict(set)
for n in range(1,N+1):
    groups[uf.find(n)].add(n)
ans=N
for _,A in groups.iteritems():
    B=set()
    for a in A:
        B.add(P[a-1])
    ans-=len(A-B)
print(ans)

Submission status: Accepted

Solution code:
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True


a,b=map(int,input().split())
*p,=map(int,input().split())
u=UNION_FIND(a)

for i in range(b):
    x,y=map(int,input().split())
    u.union(x-1,y-1)
ans=0
for i in range(a):
    ans+=(u.root(i)==u.root(p[i]-1))
print(ans)

Submission status: Accepted

Solution code:
from numpy import*
from collections import*
class UNION_FIND(object):
    def __init__(self,n):
        #親の番号を格納する。親だった場合は-(その集合のサイズ)
        #作るときはParentの値を全て-1にする
        #こうすると全てバラバラになる
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        #Aがどのグループに属しているか調べる
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])  #親を再帰で探知 再帰は最後に上のifにひっかかる
            return self.parent[x]
 
    def size(self,x):
        #自分のいるグループの頂点数を調べる
        return -self.parent[self.root(x)]   #親をとってきたい
        
    def union(self,x,y):
        #AとBをくっ付ける
        #AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        #print(self.parent)
        x=self.root(x)
        y=self.root(y)
        #print(x,y)
        if x==y:   #すでにくっついてるからくっ付けない
            return False
            
        #大きい方(A)に小さいほう(B)をくっ付けたい
        #大小が逆だったらひっくり返しちゃう。
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True


a,b=map(int,input().split())
*p,=map(int,input().split())
u=UNION_FIND(a)
d=defaultdict(list)

p=array(p)
for i in range(b):
    x,y=map(int,input().split())
    u.union(x-1,y-1)
for k,v in enumerate(u.root(i)for i in range(a)):
    d[v].append(k)
ans=0
for i in d.values():
    i=array(i)
    ans+=len(set(i+1)&set(p[i]))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

n,m = map(int,input().split())
p = list(map(int,input().split()))
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x-1,y-1)
ans = 0
for i in range(n):
    if p[i]-1 == i or uf.same(i,p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

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

UF = list(range(n+1))

def search(uf,i):
    if uf[i] == i:
        return i
    else:
        uf[i] = uf[search(uf,uf[i])]
        return uf[i]

for x,y in XY:
    i = search(UF,x)
    j = search(UF,y)
    UF[x] = min(x,y,i,j)
    UF[y] = UF[x]
    UF[i] = UF[x]
    UF[j] = UF[x]
for i in range(1,n+1):
    UF[i] = search(UF,i)
ans = 0
for p,j in zip(P,range(1,n+1)):
    if p == j:
        ans += 1
    elif UF[p] == UF[j]:
        ans += 1
print(ans)