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:
# ABC097 D - Equals
class UnionFind:
    # 最初は全てを根として初期化
    def __init__(self, n):
        self.par = [i for i in range(n)]
    
    # データxが属する木の根を再帰で取得する：root(x) = {xの木の根}
    def root(self, x):
        if (self.par[x] == x):
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    # xとyの木を併合する
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if x < y:
            self.par[ry] = rx
        else:
            self.par[rx] = ry
    # 2つのデータx, yが属する木が同じならtrueを返す
    def same(self, x, y):
        return self.root(x) == self.root(y)

n,m = map(int, input().split())
p = [int(x)-1 for x in input().split()]

ans = 0
UF = UnionFind(n)

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

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

Submission status: Accepted

Solution code:
N,M = map(int, input().strip().split(' '))
P = list(map(int, input().strip().split(' ')))
P = [p-1 for p in P]

class UnionFind:
  def __init__(self, n):
    self.tree = list(range(n))
    
  def root(self, n):
    if self.tree[n] == n:
      return n
    else:
      self.tree[n] = self.root(self.tree[n])
      return self.tree[n]
  
  def marge(self, x, y):
    if not self.root(x) == self.root(y):
      self.tree[self.root(y)] = self.root(x)
  
# グループごとに考えればよい
uf = UnionFind(N)
for _ in range(M):
  x,y = map(int, input().strip().split(' '))
  x,y = x-1,y-1
  uf.marge(x,y)

groups = [set() for _ in range(N)]
for i in range(N):
  groups[uf.root(i)].add(i)

ans = 0
for g in groups:
  if len(g) == 0: continue
  ans += len(set(P[i] for i in g) & g)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        self.par[x] = y

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

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

print(ans)

Submission status: Accepted

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

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_check(self, x, y):
        return self.find(x) == self.find(y)

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

unionUF, unionp = [set() for _ in range(N+1)], [set() for _ in range(N+1)]
for i in range(1, N+1):
    temp = UF.find(i)
    unionUF[temp].add(i)
    unionp[temp].add(p[i])

ans = 0
for i in range(len(unionUF)):
    ans += len(unionUF[i] & unionp[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n


    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

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


    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2



n, m = LI()
p = LI()
U = UnionFind(n)
for x, y in LIR(m):
    U.union(x-1, y-1)


cnt = 0
for i in range(n):
    cnt += U.same(i, p[i]-1)



print(cnt)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


uf = UnionFind(n)
for a, b in ls:
    uf.merge(a, b)
res = 0
for i in range(1, n + 1):
    p0 = uf.get_root(i)
    p1 = uf.get_root(ps[i - 1])
    if p0 == p1:
        res += 1
print(res)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


uf = UnionFind(n)
for a, b in ls:
    uf.merge(a, b)
for i in range(1, n + 1):
    uf.get_root(i)
cs = uf.parents
s0 = {c: [] for c in set(cs[1:])}
s1 = {c: [] for c in set(cs[1:])}
for i in range(1, n + 1):
    c = cs[i]
    s0[c].append(ps[i - 1])
    s1[c].append(i)

res = 0
for c in set(cs[1:]):
    res += len(set(s0[c]) & set(s1[c]))
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = list(map(int, input().split()))
e = [list(map(int, input().split())) for _ in range(M)]
res = 0
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 Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
childs = [[] for _ in range(N + 1)]
for i in range(M):
  uf.Unite(e[i][0], e[i][1])
for i in range(1, N + 1):
  childs[uf.Find_Root(i)].append(i)
for c in childs:
  temp = set([p[i - 1] for i in c])
  inter = temp & set(c)
  res += len(inter)
print(res)

Submission status: Accepted

Solution code:
# ABC097D - Equals (ARC097D)
class UnionFind:  # O(α(N))
    def __init__(self, N):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    # check i and Pi are connected components or not
    N, M, *A = map(int, open(0).read().split())
    P, E = A[:N], A[N:]
    U = UnionFind(N)  # construct a Union-Find tree (1-idx)
    for v, u in zip(*[iter(E)] * 2):  # connected components are in the same group
        U.unite(v, u)
    ans = sum(U.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    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]*n
    for i in range(m):
        x,y = LI()
        x -= 1
        y -= 1
        if root(x) != root(y):
            unite(x,y)
    ans = 0
    for i in range(n):
        if root(p[i]) == root(i):
            ans += 1
    print(ans)
    return

#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

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

Submission status: Accepted

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

for i in range(n):
    P[i] -= 1
for i in range(m):
    for j in range(2):
        X[i][j] -= 1

M = [[] for i in range(n)]

for i in range(m):
    M[X[i][0]].append(X[i][1])
    M[X[i][1]].append(X[i][0])

G = [0] * n
clr = 0

for i in range(n):
    if G[i] == 0 and len(M[i]) > 0:
        clr += 1
        G[i] = clr
        
        Q = M[i][:]
        st = 0
        while st < len(Q):
            if G[Q[st]] == 0:
                G[Q[st]] = clr
                for item in M[Q[st]]:
                    Q.append(item)

            st += 1

# print(G)

ans = 0
for i in range(n):
    if G[i] == 0 and i == P[i]:
        ans += 1

G2 = [[[], []] for i in range(clr+1)]

for i in range(n):
    G2[G[i]][0].append(i)
    G2[G[i]][1].append(P[i])
# print(G2)
# print(ans)

for i in range(1, clr+1):
    ans += len(G2[i][0]) * 2 - len(set(G2[i][0] + G2[i][1]))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        self.size = [1]*n
        self.point = n*(n-1) // 2

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        # size において rx>ry にする
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.point -= self.size[rx]*self.size[ry]
        self.size[rx] += self.size[ry]
        # ryの親をrxに設定 (sizeにおいて "小さい方(ry)を大きい方(rx)に" つなげる)
        self.par[ry] = rx
        return True

    def is_same(self, x, y):
        rx, ry = self.root(x), self.root(y)
        return rx == ry

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

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

uf = UnionFind(N)
for x, y in XY:
    uf.unite(x-1, y-1)

c = 0
for i, p in enumerate(P):
    c += uf.is_same(i, p-1)

print(c)

Submission status: Accepted

Solution code:
import collections

def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    graph = collections.defaultdict(set)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)

    sets = []
    visited = set()
    idx = [-1 for _ in range(N+1)]
    j = 0
    for a in range(1, N+1):
        if a not in visited:
            visited.add(a)
            cur = [a]
            j += 1
            idx[a] = j
            while cur:
                temp = []
                for a in cur:
                    for b in graph[a]:
                        if b not in visited:
                            visited.add(b)
                            idx[b] = j
                            temp.append(b)
                cur = temp
    # print(idx)
    count = 0
    for i in range(N):
        if idx[i+1] == idx[p[i]]:
            count += 1
    return count



if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

    # 検索
    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)
        y = self.find(y)
        if not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                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) 

def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    P = list(map(int,input().split()))
    XY = [list(map(int,input().split())) for i in range(M)]
    A = UnionFind(N)
    
    for i in range(M):
        x,y = XY[i]
        A.union(x,y)
        
    ans = 0
    for i in range(N):
        j = i+1
        p = P[i]
        if A.same_check(j,p):
            ans += 1
    print(ans)
    
    
    
main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg
    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    n,m=map(int, input().split())
    pd = [-1] * (n + 1)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    p=list(map(int, input().split()))
    for _ in range(m):
        x,y=map(int, input().split())
        merge(x-1,y-1)
    ans=0
    for i in range(n-1,-1,-1):
        if get_group(i)==get_group(p[i]-1):
            ans+=1
    print(ans)

main()

Submission status: Accepted

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

class Union_find():
    def __init__(self, N):
        self.Group = [i for i in range(N)]
        
    def find(self,x):# find(a)=find(b)のとき同じグループ
        while self.Group[x] != x:
            x = self.Group[x]
        return x

    def Union(self,x,y):  # xとyが同じグループになるよう更新
        if self.find(x) != self.find(y):
            self.Group[self.find(y)] = self.Group[self.find(x)] = min(self.find(y),self.find(x))

A = Union_find(N)

for x,y in S:
    A.Union(x-1,y-1)

ANS = 0

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

for i in range(N):
    if A.find(i) == A.find (P[i]):
        ANS += 1

print(ANS)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC97 D

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def union(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()
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
for _ in range(m):
    x,y = LI()
    if root(x-1) != root(y-1):
        union(x-1,y-1)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

es = []

for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    #a,b = min(a,b), max(a,b)
    es.append((a,b))

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for a,b in es:
    uf.unite(a,b)


ans = 0
for i in range(N):
    if P[i]-1 == i or uf.is_same(i,P[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

def wantp(n):

    Q = []

    while True:

        if lis[n] == n:
            ans = n
            break

        else:
            Q.append(n)
            n = lis[n]

    for i in Q:
        lis[i] = ans

    return ans



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

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


lis = [0] * (2 * N + 1)

rank = [0] * (2 * N + 1)

for i in range(2 * N + 1):

    i -= N

    lis[i] = i

for i in range(N):

    lis[-p[i]] = i + 1
    rank[i + 1] = 1

for i in range(M):

    x,y = map(int,input().split())

    if x > M and y > M:
        continue;

    xp = wantp(x)
    yp = wantp(y)

    if rank[xp] > rank[yp]:

        lis[yp] = lis[xp]

    elif rank[xp] < rank[yp]:

        lis[xp] = lis[yp]

    else:

        lis[yp] = lis[xp]
        rank[xp] += 1

answer = 0

for i in range(N):

    i += 1
    if wantp(i) == wantp(-i):
        answer += 1

print (answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ps = list(map(int, input().split()))
G = list(range(N))
def getparent(n):
  if G[n] == n:
    return n
  G[n] = getparent(G[n])
  return G[n]
for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  x = getparent(x)
  y = getparent(y)
  G[x] = y
#print(G)
Ss = [set() for i in range(N)]
for i in range(N):
  j = getparent(i)
  Ss[j].add(ps[i])
#print(Ss)
r = 0
for i in range(N):
  if i+1 in Ss[G[i]]:
    r += 1
print(r)

Submission status: Accepted

Solution code:
# ABC097D - Equals (ARC097D)
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    # check i and Pi are connected components or not
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    U = UnionFind(N)  # construct a Union-Find tree (1-idx)
    for v, u in E:  # connected components are in the same group
        U.unite(v, u)
    ans = sum(U.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ARC097D - Equals
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    group[v] = color  # make vertex v searched
    for u in G[v]:  # search vertices available from v recursively
        if not group[u]:  # skip if already searched
            dfs(u, color)


def main():
    # check i and Pi are connected components or not
    global G, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # construct a graph (1-idx)
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    group = [0] * (N + 1)
    color = 1
    for v in range(1, N + 1):  # connected components are in the same group
        if not group[v]:
            dfs(v, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ARC097D - Equals (ABC097D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    seen[v] = 1  # make vertex v searched
    group[v] = color
    for u in G[v]:  # search vertices available from v recursively
        if not seen[u]:  # skip if already searched
            dfs(u, color)


def main():
    # check i and Pi are connected components or not
    global G, seen, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # construct a graph (1-idx)
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    seen, group = [0] * (N + 1), [0] * (N + 1)
    color = 1
    for i in range(1, N + 1):  # connected components have the same color
        if not seen[i]:
            dfs(i, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,math,itertools,bisect,copy,re

from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint
# 10倍速いらしい
input = sys.stdin.readline

INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N,M = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]


# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

for _ in range(M):
    x, y = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x,y)

# print(PARENT)

D1 = dict()
D2 = dict()

for i in range(N):
    grp = root(i)
    s1 = D1.get(grp, set())
    s1.add(i+1)
    D1[grp] = s1

    s2 = D2.get(grp, set())
    s2.add(P[i])
    D2[grp] = s2

# print(D1)
# print(D2)

ans = 0
for grp in set(PARENT):
    s1 = D1.get(grp, set())
    s2 = D2.get(grp, set())
    ans += len(s1 & s2)

print(ans)

Submission status: Accepted

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

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x

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

uf = UnionFind(n)
for x, y in xyxy :
    uf.union(x-1, y-1)
for i in range(n) :
    uf.find(i)

d = {}
for i, k in enumerate(uf) :
    if k not in d :
        d[k] = {i}
    else :
        d[k].add(i)

e = {}
for k, set0 in d.items():
    e[k] = set()
    for i in set0 :
        e[k].add(pp[i]-1)

ans = 0
for k in d.keys() :
    set0 = d[k]
    set1 = e[k]
    ans += len(set0&set1)

print(ans)

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind():

    #0~Nまでの頂点数で初期化していることに注意
    def __init__(self, n):
        self.n = n
        self.root = [-1] * n

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]


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

Uni = UnionFind(N)

# どことどこが繋がっているかでグループ分けする
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    # 添字の値そのまま(-1されてるけど)で、連結されているものは同じグループ
    Uni.Unite(x, y)

a = [set() for _ in range(N)]
for i in range(N):
    #　ああ！この添字はこのグループだよ！
    r = Uni.FindRoot(i)
    # 同じグループなところにその添字を突っ込む！
    a[r].add(i)

ans = 0
for i in range(N):
    for j in a[i]:
        if p[j] - 1 in a[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind():

    #0~Nまでの頂点数で初期化していることに注意
    def __init__(self, n):
        self.n = n
        self.root = [-1] * n

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

    def isSameGroup(self, x, y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self, x):
        return -self.root[self.FindRoot(x)]


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

Uni = UnionFind(N)

# どことどこが繋がっているかでグループ分けする
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    # 添字の値そのまま(-1されてるけど)で、連結されているものは同じグループ
    Uni.Unite(x, y)

a = [set() for _ in range(N)]
for i in range(N):
    #　ああ！この添字はこのグループだよ！
    r = Uni.FindRoot(i)
    # 同じグループなところにその添字を突っ込む！
    a[r].add(i)
    
ans = 0
for i in range(N):
    for j in a[i]:
        if p[j] - 1 in a[i]:
            ans += 1
print(ans)