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:
import sys
import collections
class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  # 非負なら親ノード，負ならグループの要素数

    def root(self, x):  # root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  # xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y):  # merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  # xの要素数がyの要素数より「小さい」とき入れ替える
            x, y = y, x
        self.parent[x] += self.parent[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.parent[self.root(x)]
sys.setrecursionlimit(100000000)

N,M = list(map(int,input().split(" ")))
Ps =  list(map(int,input().split(" ")))
u = UnionFind(N)
for i in range(M):
    a,b = list(map(int, input().split(" ")))
    u.merge(a,b)
ans = 0
for i in range(1,N + 1):
    if u.root(i) == u.root(Ps[i-1]):
        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()))
tree = list(range(N))

def root(n):
    O = {n}
    while True:
        if tree[n] == n:
            for o in O:
                tree[o] = n
            return n
        n = tree[n]
        O.add(n)

for i in range(M):
    x,y = map(lambda x: int(x)-1,input().split())
    rx = root(x)
    ry = root(y)
    if rx == ry:
        continue
    tree[rx] = ry

print(sum(map(lambda x: root(x)==root(P[x]),range(N))))

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 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=[int(i) for i in input().split()]

uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
ans=0
for i in range(n):
    if uf.same_check(p[i],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)]


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

    # 検索
    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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    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.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[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 count(self, x):
        return -self.root[self.find(x)]
#
#graph = [[] for _ in range(N)]
#
#for x,y in xy:
#    graph[x-1].append(y-1)
#    graph[y-1].append(x-1)
        
    
uf = UnionFind(N)
for x,y in xy:
    uf.union(x-1,y-1)
    
for i in range(N):
    uf.find(i)
    
idxlist = [[] for _ in range(N)]

for i,t in enumerate(uf.par):
    idxlist[t].append(i)
    
import bisect
ans = 0
for idxs in idxlist:
    for idx in idxs:
        tmpidx = bisect.bisect_left(idxs,P[idx]-1)
        if tmpidx >= len(idxs):continue
        if idxs[tmpidx] == P[idx]-1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
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[y] = x
        else:
            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)]

def main():
  N, M = map(int, input().split())
  p = list(map(int, input().split()))
  xy = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N+1)
  for x, y in xy:
    U.Unite(x, y)
  ans = 0
  for i in range(1, N+1):
    if U.isSameGroup(i, p[i-1]):
      ans += 1
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Accepted

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

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

    nodes = [Node() for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(nodes[a], nodes[b])
    
    ans = 0
    for i in range(N):
        if same_tree(nodes[i], nodes[p[i]-1]):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

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

	def isSame(self, x, y):
		return self.find(x) == self.find(y) or x==y
		
def solve():
	n,_,*l=map(int,open(0).read().split())
	xy=l[n:]
	ids=[0]*(n+1)
	for i in range(n):ids[l[i]]=i+1
	uf=UnionFind(n)
	for x,y in zip(*[iter(xy)]*2):uf.unite(x,y)
	print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
	
if __name__=="__main__":solve()

Submission status: Accepted

Solution code:
class uf():
    def __init__(self,n):
        self.root = [-1] * (n+1)

    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):
        rootx = self.findroot(x)
        rooty = self.findroot(y)
        if rootx == rooty:
            return
        else:
            self.root[rootx] += self.root[rooty]
            self.root[rooty] = rootx
            return

    def is_same_group(self,x,y):
        return self.findroot(x) == self.findroot(y)

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

uf = uf(N)

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

count = 0
for n in range(N):
    if uf.is_same_group(P[n],n+1):
        count += 1

print(count)

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


N, M = map(int, input().split())
p = [int(i) for i in input().split()]
uf = UnionFind(N)

for _ 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:
import sys
sys.setrecursionlimit(10 ** 9)

N,M = map(int,input().split())
P = list(map(int,input().split()))
XY = []
for i in range(M):
  XY.append(list(map(int,input().split())))
#print(XY)

E = [set() for _ in range(N+1)]
for x,y in XY:
  E[x].add(y)
  E[y].add(x)
#print(E)

def dfs(v,mark):
  visited[v] = mark
  for u in E[v]:
    if visited[u] == 0:
      dfs(u,mark)

visited = [0 for _ in range(N+1)]
mark = 1
for i in range(1,N+1):
  if visited[i] == 0:
    dfs(i,mark)
    mark += 1
#print(visited)

G = [set() for _ in range(max(visited))]
for i in range(1,N+1):
  G[visited[i]-1].add(i)
#print(G)

ans = 0
for g in G:
  Pset = set()
  for idx in g:
    Pset.add(P[idx-1])
  ans += len(Pset & g)
print(ans)

Submission status: Accepted

Solution code:

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




class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

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

num = 0
for i in range(N):
	if UF.root(i) == UF.root(p[i] - 1):
		num += 1

print(num)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False



def dsUpdate(ds):
    for x0 in ds:
        x = x0
        while ds[x] != x:
            x = ds[x]

        root = x
        x = x0

        while ds[x] != root:
            y = ds[x]
            ds[x] = root
            x = y


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

    ds = {x:x for x in range(1, N+1)}
    for x, y in [map(int, input().split()) for _ in range(M)]:
        dsUnion(ds, x, y)
        
    dsUpdate(ds)

    Q = {}
    for x, root in ds.items():
        if not root in Q:
            Q[root] = set()

        Q[root].add(x)

    cnt = 0

    for q in Q.values():
        p = set(P[x-1] for x in q)
        cnt += len(q&p)

    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

N, M = map(int,input().split())
P = list(map(int, input().split()))
X = [0] * M
Y = [0] * M

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

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

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

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[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)

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count


uf = UnionFind(N)
for i in range(M):
    uf.unite(X[i], Y[i])

#print(uf.parent)

ans = 0
for i in range(len(P)):
    p = P[i]-1
    if i==p or uf.same(i, p):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class uf_tree():

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

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    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 same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False

n,m = map(int,input().split())
arr = list(map(int,input().split()))
tree = uf_tree(n)
for i in range(m):
    a,b = map(int,input().split())
    tree.unite(a-1,b-1)

ans = 0
for i in range(n):
    if tree.same(arr[i]-1,i):
        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)]

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

uf = UnionFind(2*N)
for i in range(N):
    # 
    uf.Unite(N+i,p[i] -1)
for i in range(M):
    uf.Unite(N+xy[i][0]-1,N+xy[i][1] -1)
ans = 0
for i in range(N):
    if uf.isSameGroup(N+i,i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
   def __init__(self,n):
       self.parent = [-1 for i in range(n)]

   def find(self, x):
       if self.parent[x] < 0:
           return x

       else:
           self.parent[x] = self.find(self.parent[x])
           return self.parent[x]

   def union(self, x, y):
       x, y = self.find(x), self.find(y)
       if (x == y):
           pass
       else:
           self.parent[x] = self.parent[y]
           self.parent[y] = x

   def isgroup(self, x, y):
       return True if self.find(x) == self.find(y) else False


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

uf = UnionFind(n+1)

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

count = 0
for i in range(n):
    count += 1 if uf.isgroup(i+1, p[i]) else 0

print(count)

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 (ABC097D)
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):
        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 have the same color
        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
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:
class UnionFind():

    def __init__(self, n):
        # 頂点の値が0から始まる前提なので注意
        self.par = [i for i in range(n)]

    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
        
        self.par[x] = y
        return


def main():
    N, M = map(int, input().split())
    p = list(map(lambda x: int(x)-1, 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 uf.same(i, p[i]):
            ans += 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = list(map(lambda x: int(x)-1,input().split()))
par = [i for i in range(n)]
def root(x):
    if x==par[x]:
        return x
    else:
        par[x] =root(par[x])
        return par[x]
def union(x,y):
    x= root(x)
    y= root(y)
    if x==y:
        return
    else:
        par[x]=y

for _ in range(m):
    px,py = map(lambda x: int(x)-1,input().split())
    union(px,py)

for i in range(n):
    root(i)

dual = [(x,y) for x,y in zip(p,par)]
dual.sort(key=lambda x:x[0])
ans = 0
for i in range(n):
    if dual[i][1]==par[i]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100010)

def main():
    def input():
        return sys.stdin.readline()[:-1]

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

    p = list(map(lambda x: int(x)-1, input().split()))
    parent = [k for k in range(N)]

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

    def unite(x,y):
        parent[find(x)] = find(y)

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

    ans = 0
    for k in range(N):
        if find(k) == find(p[k]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class Unionfind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in 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 union(self, 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):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
U = Unionfind(n+1)
pn = [0]+[int(i) for i in input().split()]
cnt = -1
for i in range(m):
  a,b = map(int,input().split())
  U.union(a,b)
for i,v in enumerate(pn):
  if U.is_same(i,v):
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

n, m = map(int, input().split())
plist=list(map(int, input().split()))
uf = UnionFindVerSize(n)
#print(tlist)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x-1, y-1)
kotae=0
for i in range(n):
    if uf.is_same_group(i, plist[i]-1):
        kotae+=1
print(kotae)