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
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = input()
    k = I()
    l = []
    n = len(s)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in alp:
        for j in range(n):
            if s[j] == i:
                l.append(s[j])
                for m in range(j+1,min(j+k,n)):
                    l.append(s[j:m+1])
        l = sorted(list(set(l)))
        if len(l) >= k:break
    print(l[k-1])
#D
def D():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    p = LI()
    for i in range(n):
        p[i] -= 1
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    for i in range(m):
        x,y = LI()
        if not same(x-1,y-1):
            unite(x-1,y-1)
    for i in range(n):
        root(i)
    g = [[] for i in range(max(par)+1)]
    for i in range(n):
        g[par[i]].append(i)
        g[par[i]].append(p[i])
    ans = 0
    for i in g:
        i.sort()
        d = defaultdict(int)
        for j in i:
            d[j] += 1
            if d[j] == 2:
                ans += 1
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

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

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

def union(x,y):
    if size[x]>size[y]:
        size[x]+=size[y]
        par[y]=find(x)
    elif size[y]>size[x]:
        size[y]+=size[x]
        par[x]=find(y)
    elif size[x]==size[y]:
        size[x]+=size[y]
        par[y]=find(x)
        
for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        pass
    else:
        union(find(a),find(b))
#print(par)
ans=0
for i in range(1,N+1):
    if find(i)==find(p[i]):
        ans+=1
        #print(i,find(i))
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

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

p = [0]+p
pairs = []

for i in range(m):
    pairs.append(tuple(map(int,input().split())))


U = [0]*(n+1)
for i in range(n+1):
    U[i] = i
def find(x):
    global U
    k = x
    while U[k]!=k:
        k = U[k]
    U[x] = k
    return k

def union(x,y):
    global U
    a = find(x)
    b = find(y)
    if a != b:
        U[b] = a
for x,y in pairs:
    union(x,y)
res = 0
for i in range(1,n+1):
    if find(p[i]) == find(i):
        res += 1

print(res)

Submission status: Accepted

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

for i in range(N):
    Pi[i] = Pi[i] - 1

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

def parent(n):
    if T[n] == n:
        return n
    r = parent(T[n])
    T[n] = r
    return r

for _ in range(M):
    p1, p2 = map(int, input().split())
    p1 -= 1
    p2 -= 1
    pr1 = parent(p1)
    pr2 = parent(p2)
    if pr1 == pr2:
        continue
    T[pr2] = pr1

count = 0
for i in range(N):
    p1 = parent(Pi[i])
    p2 = parent(i)
    if p1 == p2:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


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

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

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

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


a,b =  map(int, input().split())
l = list(map(int, input().split()))
uf = UnionFind(a)
for i in range(b):
    x,y =map(int, input().split())
    x-=1
    y-=1
    uf.union(x, y)  # (3)
ans=0
for i,t in enumerate(l):
    if uf.same(t-1,i):ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    """1-index"""

    def __init__(self, n):
        self.parent = [-1] * (n + 1)  # parentは親の番号を格納。親だった時は-サイズを格納。

    # 親の番号を返す
    def root(self, A):
        if self.parent[A] < 0:
            return A
        else:
            return self.root(self.parent[A])

    # サイズを返す
    def size(self, A):
        return - self.parent[self.root(A)]

    # AとBをくっつける(直接ではなくroot(A)とroot(B)を繋げる)
    def unite(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if A == B:  # 既に同じ塊内にいる
            return False

        if self.size(A) < self.size(B):
            A, B = B, A

        self.parent[A] += self.parent[B]  # サイズを更新
        self.parent[B] = A

        return True

    # AとBが同じグループに属しているかを調べる.
    def same_check(self, A, B):
        return self.root(A) == self.root(B)


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, y)

ans = 0
for i, v in enumerate(p):
    if uf.same_check(i + 1, v):
        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()))


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


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


ans = 0
for i, p in enumerate(P):
    if UF.same(i, p):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, size: int):
        self.__size = size
        self.__data = [-1] * (size + 1)

    def unite(self, u: int, v: int):
        x, y = self.find(u), self.find(v)
        if x == y:
            return

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

    def find(self, u: int) -> int:
        if self.__data[u] < 0:
            return u
        self.__data[u] = self.find(self.__data[u])
        return self.__data[u]

    def same(self, u: int, v: int) -> bool:
        return self.find(u) == self.find(v)


def equals(N: int, M: int, P: list, XY: list) -> int:
    """例えば xi <-> xj かつ xj <-> xk の場合、xi、xj、xk は
    どの二つも交換可能である。したがって、交換可能なインデックス
    の集合をつくり、そのインデックスの集合とインデックスに対応し
    た P の部分集合との一致する部分が正しい位置における数値群と
    なる。
    """
    uft = UnionFindTree(N)
    for x, y in XY:
        uft.unite(x, y)

    return sum(1 for i, p in enumerate(P) if uft.same(i+1, p))


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    P = [int(s) for s in input().split()]
    XY = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = equals(N, M, P, XY)
    print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    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 not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

a,b = map(int,input().split())
su = 0
c = list(map(int,input().split()))
uf = UnionFind(a)
for i in range(b):
    n,m = map(int,input().split())
    uf.unite(n,m)

aaa = list(uf.grouper())

for i in range(len(aaa)):
    for j in range(len(aaa[i])):
        if uf.are_same(c[aaa[i][j]-1],aaa[i][j]):
            su += 1

print(su)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
P=list(map(int,input().split()))
par=[i for i in range(N)]
ans=0

def root(x):
    if x!=par[x]:
        par[x]=root(par[x])
    return par[x]

def connect(x,y):
    if root(x)!=root(y):
        par[root(y)]=root(x)

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

for i in range(N):
    if root(i)==root(P[i]-1):
        ans+=1

print(ans)

Submission status: Accepted

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

par=[i for i in range(N)]
rank=[1]*N

ans=0

def root(x):
    if par[x]==x:
        return x
    else:
        par[x]=root(par[x])
        return par[x]

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

def connect(x,y):
    if root(x)==root(y):
        return
    else:
        if rank[x]<rank[y]:
            x,y=y,x
        par[root(y)]=root(x)
        rank[y]+=1

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

for i in range(N):
    if same(i,P[i]-1):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys
 

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

  def root(self, x):
    if self.par[x] < 0:
      return x
    else:
      return self.root(self.par[x])

  def issame(self, x, y):
    if self.root(x) == self.root(y):
      return True
    else:
      return False
  
  def merge(self, x, y):
    x, y = [self.root(x), self.root(y)]
    if x == y:
      return False
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    return True

  def size(self, x):
    return -self.par[self.root(x)]

  def out(self):
    return self.par

if __name__ == "__main__":
  n,m = map(int, sys.stdin.readline().rstrip().split())
  p = list(map(int, sys.stdin.readline().rstrip().split()))

  uf = UnionFind(n)
  for i in range(m):
    x,y = list(map(int, sys.stdin.readline().rstrip().split()))
    x, y = x-1, y-1
    if not uf.issame(x,y):
      uf.merge(x,y)

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
input=open(0).readline
n,m=map(int,input().split())
*p,=map(int,input().split())
u=UnionFind(n+1)
for _ in range(m):
    u.unite(*map(int,input().split()))
print(sum(u.same(p[i],i+1)for i in range(n)))

Submission status: Accepted

Solution code:
#coding : utf-8

class UnionFind:
    def __init__(self, n):
        self.nodes = list(range(n))
 
    def root(self, x):
        if (self.nodes[x] == x):
            return x
        self.nodes[x] = self.root(self.nodes[x])
        return self.nodes[x]
    
    def unite(self, x, y):
        if (self.root(x) == self.root(y)):
            return
        self.nodes[self.root(x)] = self.root(self.nodes[y])
        return
    
    def same(self, x, y):
        return self.root(x) == self.root(y)

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

tree = UnionFind(n)

for _ in range(m):
    x, y = map(int, input().split())
    tree.unite(x-1, y-1)

s = 0
for i in range(n):
    if (tree.same(i, p[i] - 1)):
        s += 1
print(s)

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

# Union Find
class UnionFind():
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.sizes = [1 for _ in range(size)]
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.par[y] = x
            self.sizes[x] += self.sizes[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def size(self, x):
        return self.sizes[self.root(x)]

uf = UnionFind(n)
for x, y in xy:
    uf.unite(x-1, y-1)
mask = [0] * n
for i in range(n):
    mask[i] = uf.root(i)
res = 0
for i in range(n):
    if mask[i] == uf.par[p[i]-1]:
        res += 1
print(res)

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.parent_of = {}
        self.rank_of = {}
        for value in values:
            if value in self.parent_of:
                raise RuntimeError("Dupulicated Value Added")
            self.parent_of[value] = None
            self.rank_of[value] = 0

    def __root(self, value):
        if self.parent_of[value] is None:
            return value
        else:
            self.parent_of[value] = self.__root(self.parent_of[value])
            return self.parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.rank_of[r1] < self.rank_of[r2]:
                self.parent_of[r1] = r2
            else:
                self.parent_of[r2] = r1
                if self.rank_of[r1] == self.rank_of[r2]:
                    self.rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def groups(self):
        groups = {}
        for k in self.parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    P = [x-1 for x in map(int, input().split())]
    uft = UnionFindTree(P)
    for _ in range(M):
        p, q = [x-1 for x in map(int, input().split())]
        uft.unite(P[p], P[q])
    ans = 0
    for i in range(N):
        if uft.is_same(i, P[i]):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
x, y = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for a, b in zip(x, y):
    E[a].append(b)
    E[b].append(a)
v = [True for _ in range(N + 1)]


def f(i, P, Q):
    v[i] = False
    P.add(i)
    Q.add(p[i])
    for a in E[i]:
        if v[a]:
            f(a, P, Q)


ans = 0
for i in range(1, N + 1):
    if v[i]:
        P = set()
        Q = set()
        f(i, P, Q)
        ans += len(P & Q)
print(ans)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x
    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
n, m = map(int, input().split())
p = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
place = Unionfind(n)
d = {}
for x, y in edges:
    place.union(x-1, y-1)
loot = [0] * n
for i in range(n):
    loot[i] = place.find(i)
    if loot[i] not in d:
        d[loot[i]] = {p[i]-1}
    else:
        d[loot[i]].add(p[i]-1)
counter = 0
for i in range(n):
    if i in d[loot[i]]:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()));n,m=I();p=I();l=[i for i in range(n+1)]
def u(x):
 if l[x]!=x:l[x]=u(l[x])
 return l[x]
for _ in[0]*m:x,y=I();l[u(x)]=u(y)
print(sum(u(i)==u(j)for i,j in enumerate(p,1)))

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,size):
    self.table=[-1for _ in range(size)]
  def root(self,x):
    while self.table[x]>=0:
      x=self.table[x]
    return x
  def unite(self,x,y):
    s1=self.root(x)
    s2=self.root(y)
    if s1!=s2:
      if self.table[s1]!=self.table[s2]:
        if self.table[s1]<self.table[s2]:
          self.table[s2]=s1
        else:
          self.table[s1]=s2
      else:
        self.table[s1]-=1
        self.table[s2]=s1
    return
  def same(self,x,y):
    return self.root(x)==self.root(y)
I=lambda:list(map(int,input().split()))
n,m=I()
p=I()
u=UnionFind(n)
for _ in range(m):
  a,b=I()
  u.unite(a-1,b-1)
print(sum(u.same(i,j-1)for i,j in zip(range(n),p)))

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
P = list( map( int, input().split()))
par = [ i for i in range(N)]
 
def find(x):
    p = par[x]
    if p == x:
        return x
    a = find(p)
    par[x] = a
    return a
 
for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx
 
ans = 0
for i in range(N):
    if find(i) == find(P[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
p=[0]+list(map(int,input().split()))
from collections import defaultdict
d=defaultdict(list)
f=defaultdict(int)

for _ in range(M):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)
ans=0
for i in range(1,N+1):
    if f[i]==0:
        ind={i}
        val={p[i]}
        que=d[i]
        while len(que)>0:
            tmp=[]
            for q in que:
                if f[q]==0:
                    f[q]=1
                    ind.add(q)
                    val.add(p[q])
                    tmp+=d[q]
            que=tmp
        ans+=len(ind&val)
print(ans)

Submission status: Accepted

Solution code:
def root(nodes, x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes, nodes[x])
        return nodes[x]

def unite(nodes, x, y):
    root_x, root_y = root(nodes, x), root(nodes, y)
    if root_x != root_y:
        large_root = min(root_x,root_y)
        small_root = max(root_x,root_y)
        nodes[large_root] += nodes[small_root]
        nodes[small_root] = large_root 

N, M = map(int, input().split())
p = [int(e)-1 for e in input().split()]
# ノードは-1で初期化
nodes = [-1]*N
info = [[int(e)-1 for e in input().split()] for i in range(M)]
for x, y in info:
    unite(nodes, x, y)

group = [[] for i in range(N)]
for i in range(N):
    group[root(nodes,i)].append(i)

def deplications(list1,list2):
    before = len(list1) + len(list2)
    list3 = list(set(list1 + list2))
    after = len(list3)
    return before - after

def make_list(list1):
    list2 = [p[e] for e in list1]
    return list2

ans = 0
for pair in group:
    if pair == []:
        continue
    ans += deplications(pair,make_list(pair))

print(ans)

Submission status: Accepted

Solution code:
#ARC097-D
n,m=map(int,input().split())
P=list(map(int,input().split()))
edges=[list(map(int,input().split())) for _ in range(m)]

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

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

uf=UnionFind(n)
ans=0
for i,j in edges:
    uf.union(i,j)
for i in range(n):
    if uf.same_check(i+1,P[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(N+1)]
rank = [0] * (N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        #親を検索
        par[x] = find(par[x])
        return par[x]

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

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

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)
S = {}
for i in range(N):
    S[p[i]] = par[i+1]
ans = 0
for i in range(N):
    if same_checker(S[p[i]], S[i+1]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): # get root
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    if ia == ib:
        return 
        
    if ia < ib:
        union_list[ib] = ia
    elif ia > ib:
        union_list[ia] = ib
    


def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
P = list(map(int, input().split()))
E = defaultdict(list)

for _ in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
    E[y].append(x)

visited = [False] * (N+1)
connected = []
for i in range(1, N+1):
    if visited[i]:
        continue
    visited[i] = True
    temp = [i]
    stack = [v for v in E[i]]
    while stack:
        v = stack.pop()
        if visited[v]:
            continue
        visited[v] = True
        temp.append(v)
        stack += E[v]
    connected.append(temp)

ans = 0
for cn in connected:
    ans += len(set(cn) & set([P[i-1] for i in cn]))
print(ans)

Submission status: Accepted

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

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

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,y)
count=0
for i in range(n):
    if UF.same_check(i+1,P[i]):
        count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        # root_xのほうが要素が多い
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True
    def lists(self):
        d = defaultdict(list)
        for i in range(len(self.parent)):
            parent = self.root(i)
            d[parent].append(i)
        return d

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))
    UF = UnionFind(n)
    for i in range(m):
        x, y = list(map(int, input().split()))
        UF.union(x-1, y-1)
    ans = 0
    for indices in UF.lists().values():
        indices_set = set(indices)
        p_set = set(ps[i]-1  for i in indices)
        ans += len(p_set & indices_set)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
mapp = [[] for _ in range(n + 1)]
for xy in xys:
    mapp[xy[0]].append(xy[1])
    mapp[xy[1]].append(xy[0])

bfs = [0] * (n + 1)
count = 0
for i in range(1, n + 1):
    nexts = mapp[i]
    if not(bfs[i]):
        bfs[i] = i
    for j in nexts:
        if bfs[j]:
            continue
        bfs[j] = i
        nexts += mapp[j]
    if bfs[i] == bfs[p[i - 1]]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
p=[0]+list(map(int, input().split()))

par=[i for i in range(n+1)]
cnt=0
def root(i):
    if par[i]==i:
        return i
    else:
        par[i]=root(par[i])
        return par[i]


for i in range(m):
    x, y=map(int, input().split())
    if root(x)==root(y):
        0
        #print(par[1:])
    else:
        par[root(y)]=root(x)
        #print(par[1:])

ans=0
for i in range(n):
    n=1+i
    if root(n)==root(p[n]):
        ans=ans+1
print(ans)
'''
print(par[1:])

root_ls=[0]+[root(i+1) for i in range(n)]
print(par[1:])
print(root_ls[1:])
'''

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.par = [i for i in range(n + 1)]  # init roo

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

    def union(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.par[rx] = ry

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

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

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

cnt = 0
for i, p in enumerate(P, 1):
    if tree.same(i, p):
        cnt += 1
print(cnt)