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:
N, M = map(int, input().split())

class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(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)

u = UnionFind(N)
p_list = list(map(int, input().split()))

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

res = 0
for i in range(N):
    res += int(u.same(i, p_list[i]-1))
print(res)

Submission status: Accepted

Solution code:
import sys

def key2rep_iter(key, key2rep, temp_list):
    if key2rep[key] == key:
        for i in temp_list:
            key2rep[i] = key2rep[key]
        return key
    temp_list.append(key)
    return key2rep_iter(key2rep[key], key2rep, temp_list)

def add_x2y(x, y, key2rep):
    rep = key2rep_iter(y, key2rep, [])
    big_rep = key2rep_iter(x, key2rep, [])
    if rep == big_rep:
        return
    key2rep[big_rep] = rep

N, M = map(int,input().split(' '))
p_list = [int(i) for i in input().split(' ')]
key2rep = {i+1:i+1 for i in range(N)}

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), key2rep)

print(len([1 for i in range(N) if key2rep_iter(p_list[i], key2rep, []) == key2rep_iter(i+1, key2rep, [])]))

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):
        s1 = self.find(x)
        s2 = self.find(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

n,m = map(int,raw_input().split())

arr = map(int,raw_input().split())

uf = UnionFind(n)

for i in range(m):
    f,t = map(int,raw_input().split())
    f -= 1
    t -= 1
    uf.union(f,t)

ans = 0
for i in range(n):
    if uf.find(i) == uf.find(arr[i]-1):
        ans += 1

print ans

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import *

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

class union_find:
  def __init__(self, n):
    self.par = [-1] * n
  def __repr__(self):
    return "union_find({0})".format(self.par)
  def unite(self, x, y):
    if self.root(x) != self.root(y):
      self.par[self.root(x)] = y
  def root(self, x):
    if self.par[x] == -1:
      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)
  
N, M = reads()
p = reads()

uf = union_find(N)
for _ in range(M):
  x, y = reads()
  uf.unite(x-1, y-1)

d = defaultdict(set)
for i in range(N):
  d[uf.root(i)].add(i)
print(d, file=stderr)

ans = 0
for grp in d.values():
  ans += len(grp & {p[i]-1 for i in grp})
print(ans)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
p = [ int(i) -1 for i in input().split()]
edges = [ [] for _ in range(N)]
visit = [None] * N
ans = 0
for i in range(M):
    x,y = list(map(int,input().split()))
    edges[x -1].append(y -1)
    edges[y -1].append(x -1)
for i in range(N):
    if visit[i]:
        continue
    stack = [i]
    cp = [i]
    visit[i] = "yes"
    while len(stack) > 0:
        t = stack.pop()
        for tt in edges[t]:
            if visit[tt] is None:
                visit[tt] = "yes"
                cp.append(tt)
                stack.append(tt)
    nodes = set()
    for node in cp:
        nodes.add(p[node])
    for node in cp:
        if node in nodes:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
def root(R, a):
    if R[a] != a:
        R[a] = root(R, R[a])
    return R[a]

def union(R, x, y):
    a = root(R, x)
    b = root(R, y)
    if a != b:
        R[a] = b


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

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

count = 0
for i in range(N):
    if root(R, i) == root(R, p[i] - 1):
        count += 1

print(count)

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self,n):
		self.par=[i for i 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 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())
uf=UnionFind(n)
p=[int(i)-1 for i in input().split()]
for _ in range(m):
	x,y=map(int,input().split())
	uf.union(x-1,y-1)
print([uf.same_check(i,p[i]) for i in range(n)].count(True))

Submission status: Accepted

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

class UF:
  def __init__(self,size):
    self.table= [-1]*(size+1)
    
  def unite(self,a,b):
    tmp1 = self.search(a)
    tmp2 = self.search(b)
    if tmp1 != tmp2:
      self.table[tmp2] = tmp1 
    
  def search(self,z):
    if self.table[z] < 0:
      return z
    else:
      tmp = z
      while 1:
        if self.table[tmp] < 0:
          self.table[z] = tmp
          return tmp
        tmp = self.table[tmp]

union = UF(n)
for node in nodes:
  union.unite(node[0],node[1])
result = 0
for i in range(n):
  if union.search(nums[i]) == union.search(i+1):
    result += 1
print(result)

Submission status: Accepted

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

union = {x:x for x in range(1, n+1)}
def root(n):
    if union[n] == n:
        return n
    union[n] = root(union[n])
    return union[n]

for x,y in xs:
    union[root(x)] = root(y)

print(sum(root(i+1) == root(ps[i]) for i in range(n)))

Submission status: Accepted

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Accepted

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

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

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

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.par[i] = j
        else:
            self.par[j] = i
            if self.rank[i] == self.rank[j]:
                self.rank[i] += 1

    def same(self, i, j):
        return self.root(i) == self.root(j)


union_find = UnionFind(N)


sets = []
for _ in range(M):
    x, y = map(lambda x: int(x)-1, input().split())
    union_find.union(x, y)


res = 0

for i, n in enumerate(p):
    if union_find.same(i, n):
        res += 1

print(res)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,size):
        self.L = [{'parent':i,'rank':0} for i in range(size)]

    def find(self,x):
        if self.L[x]['parent'] != x:
            self.L[x]['parent'] = self.find(self.L[x]['parent'])
        return self.L[x]['parent']

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.L[x_root]['rank'] < self.L[y_root]['rank']:
            x_root,y_root = y_root,x_root

        self.L[y_root]['parent'] = x_root
        if self.L[x_root]['rank'] == self.L[y_root]['rank']:
            self.L[x_root]['rank'] += 1
    
    def __str__(self):
        return str([i['parent'] for i in self.L])

if __name__ == '__main__':
    N,M = map(int,input().split())
    P = list(map(int,input().split()))
    graph = UnionFind(N)
    for i in [None]*M:
        x,y = map(int,input().split())
        graph.union(x-1,y-1)
    count = 0
    for i,v in enumerate(P):
        if graph.find(i) == graph.find(v-1):
            count += 1
    print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  2 16:19:14 2018

@author: hhh
"""

n,m=map(int,input().split())
p=list(map(int,input().split()))
f=[i for i in range(0,n)]
def F(x):
    if x==f[x]:
        return x
    else:
        f[x]=F(f[x])
        return f[x]
    
for i in range(0,m):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    if F(x)!=F(y):
        f[f[x]]=f[y]

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
        self.diff_potential = [0 for i in range(size)]#親ノードを基準としたポテンシャル

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) #xをxの根rxに直接つなぎたい
            self.diff_potential[x] += self.diff_potential[self.parent[x]] #そのために，diff(rx,x)を計算
            self.parent[x] = rx #xをrxに直接つなげる
            return rx

    def merge(self, x, y, diffxy): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        diffxy = self.diff_potential[x] + diffxy - self.diff_potential[y] #diffxyをdiff(rx,ry)で置き換え
        x = self.root(x) #rxを新たにxと名づける
        y = self.root(y) #ryを新たにyと名づける
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
            diffxy = -diffxy
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_potential[y] = diffxy #yの相対ポテンシャルを更新
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y): #この時点でxの親はroot(x)
            return self.diff_potential[y] - self.diff_potential[x]
        else:
            return None

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return 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，違うならFalse
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

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

    def union(self, x, y): #union(i,j): $i$のいるグループと$j$のいるグループをまとめる
        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(i,j): $i$と$j$ が同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(i): $i$のいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

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

    def union(self, x, y): #union(i,j): $i$のいるグループと$j$のいるグループをまとめる
        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 same(self, x, y): #same(i,j): $i$と$j$ が同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(i): $i$のいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

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

    def union(self, 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 same(self, x, y):
        return self.root(x) == self.root(y)



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

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

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

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

    def union(self, 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 same(self, x, y):
        return self.root(x) == self.root(y)



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

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

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

print(ans)

Submission status: Accepted

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

    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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
N,M = map(int,input().split())
tree = Unionfindtree(N)
P =[int(i) for i in input().split()]
for i in range(M):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)
    
ans = 0
for i in range(N):
    if tree.connect(P[i]-1,i):
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

N,W = map(int,input().split())
Graph = UnionFind(N)
P = [int(i) for i in input().split()]
for i in range(W):
    a ,b = map(int,input().split())
    Graph.union(a-1,b-1)
ans = 0 
for i in range(N):
    if Graph.find(P[i]-1) == Graph.find(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
p=i2()

import sys
sys.setrecursionlimit(10000)

par=[i for i in range(n)]
rank=[0 for i in range(n)]

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

def un(x,y):
    x=rt(x)
    y=rt(y)
    if x==y:
       return
    else:
       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]=i2()
 un(x-1,y-1)

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

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
p=i2()

import sys
sys.setrecursionlimit(10000)

par=[i for i in range(n)]
rank=[0 for i in range(n)]

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

def un(x,y):
    x=rt(x)
    y=rt(y)
    if x==y:
       return
    else:
       if rank[x]<rank[y]:
          par[x]=y
       else:
          par[y]=x
          if rank[x]==rank[y]:
             rank[x]+=1
def find(x,y):
    return  rt(x)==rt(y)
       
for i in range(m):
 [x,y]=i2()
 un(x-1,y-1)

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

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
p=i2()

import sys
sys.setrecursionlimit(10000)

par=[i for i in range(n)]
rank=[0 for i in range(n)]

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

def un(x,y):
    x=rt(x)
    y=rt(y)
    if x==y:
       return
    else:
       if rank[x]<rank[y]:
          par[x]=y
       else:
          par[y]=x
          if rank[x]==rank[y]:
             rank[x]+=1
xy=[]
for i in range(m):
 xy.append(i2())
 
for i,j in xy:
 un(i-1,j-1)
for i,j in xy:
 un(i-1,j-1)
s=0
for i in range(n):
 if par[i]==par[p[i]-1]:
   s+=1
print(s)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    p = LI_()
    a = [LI_() for _ in range(m)]
    uf = UnionFind(n)
    for x,y in a:
        uf.union(x,y)
    r = 0
    for i in range(n):
        if uf.find(i) == uf.find(p[i]):
            r += 1

    return r



print(main())

Submission status: Accepted

Solution code:

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y) :
            return
        self.par[x] = 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 index in range(n):
    start = index + 1
    to = p[index]
    if uf.same(start, to):
        count += 1
print(count)

Submission status: Accepted

Solution code:
#coding: utf-8
import math

class UnionFind():
    def __init__(self,r):
        self.size = [1] * (r+1)
        self.rank = [0] * (r+1)
        # self.root_pointer = [i for i in range(r+1)]
        self.table = [-1 for _ in range(r+1)]

    # xが属す集合の根を求める
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            # グラフの高さが異なる場合
            if self.table[root_x] != self.table[root_y]:
                if self.table[root_x] < self.table[root_y]:
                    self.table[root_y] = root_x
                else:
                    self.table[root_x] = root_y
            # グラフの高さが同じ場合
            else:
                self.table[root_x] += -1
                self.table[root_y] = root_x
        return

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

if __name__ == "__main__":
    N,M = map(int,input().split(" "))
    uf = UnionFind(N)
    P = map(int, input().split(" "))
    for _ in range(M):
        x,y = map(int, input().split(" "))
        # unionfindを作成
        uf.union(x,y)
    
    result = 0
    for i,o in enumerate(P):
        if uf.issame_root(o,i+1):
            result += 1
    
    print(result)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[i for i in range(size)]
        self.rank=[0 for _ in range(size)]
        
    def find(self,x):
        if self.table[x]==x:
            return x
        else:
            self.table[x]=self.find(self.table[x])
            return self.table[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.table[x]=y
        else:
            self.table[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)
            
            

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

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

ans=n

for i in range(n):
    if un.find(p[i]-1)!=un.find(i):
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
class Elements:
    s = set()

    def __init__(self, *elements):
        self.s = set(elements)

    def add(self, x):
        self.s.add(x)

    def remove(self, x):
        self.s.remove(x)

    def union(self, e):
        self.s |= e.s


class Hoge:
    h = {}
    elements_set = set()

    def add(self, at, new_item):
        self.h[at].add(new_item)
        self.h[new_item] = self.h[at]

    def union(self, x, y):
        if len(self.h[y].s) > len(self.h[x].s):
            x, y = y, x

        self.h[x].union(self.h[y])
        self.elements_set.remove(self.h[y])
        for i in self.h[y].s:
            self.h[i] = self.h[x]

    def new_pair(self, x, y):
        u = Elements(x, y)
        self.h[x] = u
        self.h[y] = u
        self.elements_set.add(u)

    def add_pair(self, x, y):
        if x in self.h:
            if y in self.h:
                if self.h[x] is self.h[y]:
                    pass
                else:
                    self.union(x, y)
            else:
                self.add(x, y)
        else:
            if y in self.h:
                self.add(y, x)
            else:
                self.new_pair(x, y)

    def equals(self, *l):
        result = 0

        # 動かさなくても条件を満たすものを数える
        for i, x in enumerate(l):
            if i == x and x not in self.h:
                result += 1

        # 互換の適用によって条件を満たせるものを数える
        for es in self.elements_set:
            s = es.s
            for x in s:
                if l[x] in s:
                    result += 1

        return result


def main():
    n, m = map(int, input().split())
    l = map(lambda s: int(s)-1, input().split())
    hoge = Hoge()
    for i in range(1, m + 1):
       pair = map(lambda s: int(s)-1, input().split())
       hoge.add_pair(*pair)
    print("{0:d}".format(hoge.equals(*l)))


main()