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:
class UF:
    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 find(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
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())
###############################################################
n,m=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for _ in range(m)]
x=[t[0] for t in xy]
y=[t[1] for t in xy]

uf=UF(n)
for i in range(m):
    uf.union(x[i]-1,y[i]-1)
ans=0
for i in range(n):
    if p[i]==i+1:
        ans+=1
    elif uf.find(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


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

ans = 0
for i in range(N):
    if t.find(p[i]) == t.find(i+1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def searchP(dic,x):
    p =dic[x]['p'] 
    if p==x:
        return x
    dic[x]['p']= searchP(dic,p)
    return dic[x]['p']

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

dic={i:{'p':i,'length':0} for i in range(1,N+1)}
for i in range(M):
    x,y=list(map(int,input().split()))
    x=searchP(dic,x)
    y=searchP(dic,y)
    
    if dic[x]['length']<dic[y]['length']:
        dic[x]['p']=y
    else:
        dic[y]['p']=x

group={}
ans=0
for i,v in enumerate(arr):
    if searchP(dic,v)== searchP(dic,i+1):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if self.rank[a] < self.rank[b]:
            self.parent[a] = b
        else:
            if self.rank[a] == self.rank[b]:
                self.rank[a] += 1
            self.parent[b] = a


N, M = map(int, input().split())
uf = UnionFind(N)
p = list(map(int, input().split()))
for i in range(N):
    p[i] -= 1

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

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

print(num)

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)]
rank = [0]*n

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

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

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

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

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
P=[int(i)-1 for i in input().split()]
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(a[i],b[i])
ans=0
for i in range(N):
    if same(i,P[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n)}
def U(x):
  if D[x]!=x:
    D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x-1)]=U(y-1)
print(sum(U(i)==U(p-1)for i,p in enumerate(P)))

Submission status: Accepted

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:

			if self.tree[xr]==self.tree[yr]:
				self.tree[xr]-=1
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Accepted

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			self.tree[x]=self.find(self.tree[x])
			return self.tree[x]
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Accepted

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			return self.find(self.tree[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		ans += a.find(x)==a.find(li[x])
	return ans
print(main())

Submission status: Accepted

Solution code:
class unionFind():
	def __init__(self,n):
		self.tree=[-1]*n
	def find(self,x):
		if self.tree[x]<0:
			return x
		else:
			return self.find(self.tree[x])
	def union(self,x,y):
		xr=self.find(x)
		yr=self.find(y)
		if xr!=yr:
			if self.tree[xr]<self.tree[yr]:
				self.tree[yr]=xr
			elif self.tree[xr]>self.tree[yr]:
				self.tree[xr]=yr
			else:
				self.tree[xr]-=1
				self.tree[yr]=xr
			return True
		
		return False
def main():
	ans=0
	n,m=map(int,input().split())
	a=unionFind(n)
	li=[x-1 for x in list(map(int,input().split()))]
	for _ in range(m):
		x,y=map(int,input().split())
		a.union(x-1,y-1)
	for x in range(n):
		if a.find(x)==a.find(li[x]):
			ans+=1
	return ans
print(main())

Submission status: Accepted

Solution code:
I=lambda:[int(i)for i in input().split()]
n,m=I()
P=I()
D={i:i for i in range(n+1)}
def U(x):
  if D[x]!=x:D[x]=U(D[x])
  return D[x]
for _ in [0]*m:
  x,y=I();D[U(x)]=U(y)
print(sum(U(i)==U(p)for i,p in enumerate(P,1)))

Submission status: Accepted

Solution code:
I=lambda:[int(i) for i in input().split()]
n, m = I()
P = I()
D = {i:i for i in range(n+1)}

def U(x):
  if D[x] != x:
    D[x] = U(D[x])
  return D[x]

for _ in range(m):
  x, y = I()
  D[U(x)] = U(y)

print(sum(U(i)==U(p) for i, p in enumerate(P,1)))

Submission status: Accepted

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

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

for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sdin = sys.stdin.readline

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
        else:
            self.par[ry] = rx
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

    

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


root_node = defaultdict(list)

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

for i in range(N):
    uf.find(i)
    
par = uf.par

for i,root in enumerate(par):
    root_node[root].append(i)
    
ans = 0
for node_list in root_node.values():
    num_list = []
    for i in node_list:
        num_list.append(P[i]-1)
    
    ans += len(set(node_list)&set(num_list))
            
print(ans)

Submission status: Accepted

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

par = [i for i in range(N)]
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        pass
    else:
        par[x] = y

for i in range(M):
    xi, yi = map(int, input().split())
    unite(xi - 1, yi - 1)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(int(x) - 1 for x in input().split())
s = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

a = {i:i for i in range(n)}

def root(t):
    if a[t] == t:
        return t
    else:
        a[t] = root(a[t])
        return  a[t]

for x, y in s:
    a[root(x)] = root(y)
    
ans = 0
for i in range(n):
    if root(i) == root(p[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def root(x):
    if(group[x] == x):
        return(x)
    else:
        group[x] = root(group[x])
        return(group[x])


def unite(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return

    if(rank[x] < rank[y]):
        group[x] = y
    else:
        group[y] = x
        if(rank[x] == rank[y]):
            rank[x] += 1


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


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

group = [i for i in range(N)]
rank = [0 for i in range(N)]

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


ans = 0
for i in range(N):
    if(same(i, N_list[i]) is True):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Union(x,y):	#xとyを繋げる
	x = Find(x)
	y = Find(y)

	if x == y:
		return

	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False

N,M = inpl()

table = [i for i in range(N)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(N)]	#木の長さ

pp = inpl()

for i in range(M):
	x,y = inpl()
	x -= 1
	y -= 1
	Union(x,y)

ans = 0
for i in range(N):
	if Check(pp[i]-1,i):
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sdin = sys.stdin.readline

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)

    

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


root_node = defaultdict(list)

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

for i in range(N):
    uf.find(i)
    
par = uf.par

for i,root in enumerate(par):
    root_node[root].append(i)
    
ans = 0
for node_list in root_node.values():
    num_list = []
    for i in node_list:
        num_list.append(P[i]-1)
    
    ans += len(set(node_list)&set(num_list))
            
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


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

def unite(x,y):
    x = Find(x)
    y = Find(y)
    a = rank[x]
    b = rank[y]
    forest[x] = y


def Find(x):
    if forest[x] != x:
        rank[x] = 1
        forest[x] = Find(forest[x])
        return forest[x]
    else:
        return x
    
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1
    
    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#coding:utf-8

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

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for i 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 1
        return 0


cnt = 0
tree = UnionFind3(n)
for i in range(m):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)

for i in range(n):
    a = tree.find(i)
    b = tree.find(List[i]-1)
    if a == b:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def m():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    g = [[] for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    color = [-1] * (n+1)

    def dfs(v, c):
        s = []
        s.append(v)
        color[v] = c
        while len(s) != 0:
            a = s.pop()
            for elem in g[a]:
                if color[elem] == -1:
                    dfs(elem, c)

    k = 0
    for i in range(1, n):
        if color[i] == -1:
            dfs(i,k)
            k +=1
    ans = 0
    for i in range(n):
        if color[p[i]] == color[i+1]:
            ans +=1
    return ans

print(m())

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = []
for i in range(m):
    g.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in g:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
x =  [0]*n
for i in range(n):
  x[p[i]-1] = i+1
ans = 0
#Union find
y = [-1] * n
for i in range(0,n):
  if y[i] == -1:
    y[i] = i
  c = l[i+1]
  while len(c) > 0:
    z = c.pop()
    y[z-1] = y[i]
    for j in range(len(l[z])):
      if y[l[z][j]-1] == -1:
        c.append(l[z][j])
    l[z] =[]
    
for i in range(n):
  c = x[i]
  if y[c-1] == y[i]:
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
def ge(x):
    return int(x) - 1


(n, m) = tuple(map(int, input().split()))
inp = list(map(ge, input().split()))
arr = [i for i in range(n)]


def root(a):
    global arr
    if arr[a] == a:
        return a
    else:
        tmp = root(arr[a])
        arr[a] = tmp
        return tmp


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


def merge(x, y):
    global arr
    if not sameroot(x, y):
        arr[root(y)] = root(x)


for i in range(m):
    merge(*tuple(map(ge, input().split())))

res = 0
for i in range(n):
    if sameroot(i, inp[i]):
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
p.insert(0,0)
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

link = [[] for _ in  range(N+1)]
for i in range(M):
  x = pairs[i][0]
  y = pairs[i][1]
  link[x].append(y)
  link[y].append(x)


ans = 0
visited = set()
#数列の１つ１つの数字について
for i in range(1, N+1):

  #既に1度見た数字は飛ばす
  if i in visited:
    continue
  
  #linkedに交換可能なひとまとまりの数字をセットとして格納
  #ここでlinkedをリセット
  linked = set()

  #todoにはリンク先を調べないといけない数字のリストを格納
  todo = [i]
  while todo:

    #todoから1つずつ
    cur = todo.pop()
    for dest in link[cur]:

      #既にグループに入っている数字は飛ばす
      if dest not in linked:
        linked.add(dest)
        todo.append(dest)

  #「位置」を表すグループと「数字」を表すグループのオーバーラップ部分を数える
  ans += len(linked & set(p[n] for n in linked))
  #一度見た数字は再訪しない
  visited |= linked

#最後にまだ一度も見ていない数字のなかで、i = p[i]であるものを探す
for i in set(range(1,N+1)) - visited:
  ans += i == p[i]

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        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:
            self.par[x]=y
 
n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]
 
uf=UnionFind(n)
for pi in pair:
    uf.unite(pi[0],pi[1])
 
cnt=0
for i, pi in enumerate(p):
    if uf.same(i,pi):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        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:
            self.par[x]=y

n, m=map(int, input().split())
p=[int(s)-1 for s in input().split()]
pair=[[int(s)-1 for s in input().split()] for _ in range(m)]

uf=UnionFind(n)
for pi in pair:
    uf.unite(pi[0],pi[1])

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n+1)]
rank = [0]*(n+1)
ans = 0

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

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

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

for i in range(n):
  ans += (find(p[i]) == find(i+1))

print(ans)

Submission status: Accepted

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

union = {node:node for node in range(n)}
depth = {node:0 for node in range(n)}

def root(node):
    if union[node] == node:
        return union[node]
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    a, b = sorted((root(x), root(y)), key=lambda z:depth[z])
    union[a] = b
    depth[b] = max(depth[b], depth[a]+1)

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

Submission status: Accepted

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

union = {node:(node, 0) for node in range(n)}

def root(node):
    if union[node][0] == node:
        return union[node]
    union[node] = root(union[node][0])
    return union[node]

def unite(*roots):
    r1, r2 = sorted(roots, key=lambda x:x[1])
    rank = max(r1[1]+1, r2[1])
    r = (r2[0], rank)
    union[r1[0]] = union[r2[0]] = r

for x, y in xys:
    unite(root(x), root(y))

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

Submission status: Accepted

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

union = {node:node for node in range(n)}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

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

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

Submission status: Accepted

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

print(sum(root(i) == root(p) for i, p in enumerate(ps)))

Submission status: Accepted

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node):
    if union[node] == node:
        return node
    union[node] = root(union[node])
    return union[node]

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

groups = {node:{node} for node, rootn in union.items() if node==rootn} 
for node in nodes:
    if node in groups:
        continue
    group = groups[root(node)]
    group.add(node)
    groups[node] = group

print(sum(p in groups[i] for i, p in enumerate(ps)))

Submission status: Accepted

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

nodes = range(n)
union = {node:node for node in nodes}

def root(node, previouss=None):
    if not previouss:
        previouss = []

    if union[node] == node:
        for previous in previouss:
            union[previous] = node
        return node
    else:
        previouss.append(node)
        return root(union[node], previouss)

for x, y in xys:
    rx = root(x)
    ry = root(y)
    union[rx] = ry

groups = {node:{node} for node, rootn in union.items() if node==rootn} 
for node in nodes:
    if node in groups:
        continue
    group = groups[root(node)]
    group.add(node)
    groups[node] = group

print(sum(p in groups[i] for i, p in enumerate(ps)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
graph = [[] for i in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
group = [0] * (n + 1)
ans = 0

for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if not group[point]:
            group[point] = i
            space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    p = list(map(int, input().split()))
    for i in range(N):
        p[i] -= 1
    x = [0 for _ in range(M)]
    y = [0 for _ in range(M)]
    for i in range(M):
        x[i], y[i] = map(int, input().split())
        x[i] -= 1
        y[i] -= 1

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if x!=y:
            Parent[x] = y

    Parent = [i for i in range(N)]
    for i in range(M):
        unite(x[i], y[i])

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

    return count

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

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())
*p, = map(int, input().split())
xy = [map(int,input().split()) for _ in range(M)]
result = 0

union = UnionFind(N)
for x,y in xy:
    union.union(x-1,y-1)

for i in p:
    if union.same_check(p[i-1]-1,i-1):
        result += 1

print(result)

Submission status: Accepted

Solution code:
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 find(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 = map(int, input().split())
uft = UnionFind(n)
p = list(map(int, input().split()))
rev = {x: i for i, x in enumerate(p)}

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

ans = 0
for i, x in enumerate(p):
    if uft.find(i, x - 1):
        ans += 1

print(ans)