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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = list(map(int,input().split()))
root = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    root[x].append(y)
    root[y].append(x)
    
can_move = [[i] for i in range(n+1)]

for i in range(1, n+1):
    heap = [i]
    flag = 0
    while len(heap):
        v = heap[0]
        for t in root[v]:
            if t not in can_move[i] and i != t:
                can_move[i].append(t)
                heap.append(t)
            if t == p[i-1]:
                flag = 1
                break
        if flag:
            break
        heap.pop(0)

cnt = 0
for i, pi in enumerate(p):
    if pi in can_move[i+1]:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
n,m = map(int,input().split())
p = list(map(int,input().split()))
base = 0
basemap = []
for i in range(n):
	if (i+1) == p[i]:
		base += 1
		basemap.append(i+1)

branch = dict()
for i in range(1,n+1):
	branch[i] = []

for i in range(m):
	x,y = map(int,input().split())
	branch[x].append(y)
	branch[y].append(x)
compare = [0 for i in range(n+1)]
for i in range(1,n+1):
	if branch[i] != []:
		compare[i] = 1

arrival = [0 for i in range(n+1)]
ans = []
q = []

while arrival != compare:
	counter = base
	for i in range(1,n+1):
		if arrival[i] == 0 and compare[i] == 1:
			q.append(i)
			arrival[i] = 1
			break
	section = [q[0]]
	while len(q) > 0:
		next = branch[q[0]]
		for i in range(len(next)):
			if arrival[next[i]] == 0:
				section.append(next[i])
				arrival[next[i]] = 1
				q.append(next[i])
		q.pop(0)
	psec = []
	for i in range(len(section)):
		psec.append(p[section[i]-1])
	t = section + psec + basemap
	search = collections.Counter(t)
	for i in search:
		if search[i] == 2:
			 counter += 1
	ans.append(counter)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
l = map(int, raw_input().split())
N = l[0]
M = l[1]

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

xylist =[]
for i in range(M):
    xylist.append(map(int, raw_input().split()))
    
# print(N)
# print(M)
# print(pl)
# print(xl)
# print(yl)

while True:
    oldxylist = xylist[:]
    setlist = []
    while len(xylist) > 0:
        newset = set(xylist.pop(0))
        reserve = []
        for xy in xylist:
            nextset = set(xy)
            if len(newset.intersection(nextset)) > 0:
                newset = newset.union(nextset)
            else:
                reserve.append(xy)
        xylist = reserve
        setlist.append(list(newset))
    xylist = setlist

    if oldxylist == xylist:
        break
    
score = 0
for i, p in enumerate(pl, 1):
    if i == p :
        score += 1
        continue
    
    targetlist = filter(lambda x: i in x, setlist)
    if(len(targetlist) == 0):
        continue

    targetset = targetlist[0]

    for tar in targetset:
        if(pl[tar-1] == i):
            score += 1
            break

print(score)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,m = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
c,d,e = [[] for i in range(n+1)],[True for i in range(n+1)],[]
d[0],ans = False,0
for i,j in x:
	c[i].append(j)
	c[j].append(i)
while sum(d)!=0:
	for i in range(n+1):
		if d[i]: break
	num2 = set([i])
	while True:
		num3 = deepcopy(num2)
		for i2 in list(num2):
			for j in c[i2]:
				if d[j]:
					num3.add(j)
					d[j] = False
		if num2==num3: break
		else: num2 = num3
	for i in num2: d[i]=False
	e.append(list(num2))
for i in e:
	for j in i:
		if p[j-1] in i: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,m = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
c,d,e = [[] for i in range(n+1)],[True for i in range(n+1)],[]
d[0],ans = False,0
for i,j in x:
	c[i].append(j)
	c[j].append(i)
while sum(d)!=0:
	for i in range(n+1):
		if d[i]: break
	num2 = set([i])
	while True:
		num3 = deepcopy(num2)
		for i2 in list(num2):
			for j in c[i2]: num3.add(j)
		if num2==num3: break
		else: num2 = num3
	for i in num2: d[i]=False
	e.append(list(num2))
for i in e:
	for j in i:
		if p[j-1] in i: ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = list(map(int, sys.stdin.readline().strip().split()))
ps = list(map(int, sys.stdin.readline().strip().split()))

reps = []
for i in range(M):
    reps.append(list(map(int, sys.stdin.readline().strip().split())))

# print(N, M)
# print(ps)
# print(reps)

def search(path, goal, ops):
    # print(path, goal)
    cur = path[-1]
    if cur == goal:
        return True

    r = False
    for op in ops:
        if op[0] == cur and op[1] not in path:
            r = search(path + [op[1]], goal, ops)
            if r: return r
        if op[1] == cur and op[0] not in path:
            r = search(path + [op[0]], goal, ops)
            if r: return r
    return r

cnt = 0
for i in range(N):
    x = ps[i]
    if search([i+1], x, reps):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    root[x].append(y)
    root[y].append(x)
    
can_move = [[i] for i in range(n+1)]

for i in range(1, n+1):
    heap = [i]
    while len(heap):
        v = heap[0]
        for t in root[v]:
            if t not in can_move[i] and i != t:
                can_move[i].append(t)
                heap.append(t)
        heap.pop(0)

cnt = 0
for i, pi in enumerate(p):
    if pi in can_move[i+1]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)

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

ans = 0
for i, p in enumerate(p_list):
    if uf.same(p - 1, i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        要素xが属するグループの根を返す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        要素xが属するグループと要素yが属するグループを併合
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        """
        要素xが属するグループのサイズを返す
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        要素x, yが同じグループかどうか
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        要素xが属するグループの要素をリストで返す
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        すべての根の要素をリストで返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        グループの数を返す
        """
        return len(self.roots())

    def all_group_members(self):
        """
        {ルート要素: [そのグループの要素, ...], ...}を返す
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        print()での表示用
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
N, M = map(int, input().split())
uf = UnionFind(N)
P = list(map(int, input().split()))
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    uf.union(P[a] - 1, P[b] - 1)

res = 0
for i, p in enumerate(P):
    if uf.same(p - 1, i):
        res += 1

print(res)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int, input().split())
p = list(map(int, input().split()))
x = [list(map(int, input().split())) for _ in range(m)]

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

Submission status: Accepted

Solution code:
# Union Find
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # x < y にする
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


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


n, m = map(int, input().split())
par = [-1] * n

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

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

print(sum(same(i, l[i] - 1) for i in 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 unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

  def same(self, x, y):
    return self.find(x) == self.find(y)
  
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.unite(x,y)
  
Ans=0
  
for i in range(1,N+1):
  if UF.same(P[i-1],UF.par[i]):
    Ans+=1

print(Ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n,m=map(int,input().split())
uf=UnionFind(n)
p=list(map(int,input().split()))
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x-1,y-1)
  
ans=0
for i in range(n):
  if uf.same(p[i]-1,i):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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 = na()
p = na()
count = 0
uf = UnionFind(N)

for i in range(M):
    x, y = na()
    x -= 1
    y -= 1
    uf.Unite(x, y)

for i in range(N):
    uf.Find_Root(i)

for i in range(N):
    if p[i] == i + 1:
        count += 1
    else:
        if uf.isSameGroup(p[i] - 1, p[p[i] - 1] - 1):
            count += 1
print(count)

Submission status: Accepted

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

# parentsには根の要素番号（自身が根の場合は、要素数（マイナスの値））が入る
parents = [-1] * (n + 1)
def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

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

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

# 同じグループ内では好きに入れ替えられる
ans = 0
for i,P in enumerate(p, 1):
    if i == P or same(i, P):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*(n+1)  # 頂点番号とindexをそろえるためにn+1。idx0は使わない
        self.rank = [0]*(n+1)

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])  # 再帰で根までたどる.その過程で根とつなぎかえる
            return self.par[x]

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

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

    def same_check(self, x, y):
        return self.find(x) == self.find(y)  # 根同じならTrue違うならFalseを返す

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


n, m = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x, y)

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n, m = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

#dic[root] -> [i1, i2, ...]
dic_idx = dd(set)
#dic[root] -> [p1, p2, ...]
dic_p = dd(set)
visited_root = set()

for i, p in enumerate(P):
    root = uf.find(i)
    visited_root.add(root)
    dic_idx[root].add(i)
    dic_p[root].add(p)

#print(dic_idx)
#print(dic_p)
#print(visited_root)

ans = 0
for root in list(visited_root):
    #print(root, dic_idx[root] & dic_p[root])
    ans += len(dic_idx[root] & dic_p[root])
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
par = list(range(n))
size = [1] * n
def find(x):
    """ 根のノードの値を見つけて返す """
    if x != par[x]:
        par[x] = find(par[x])
    return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return False
    else:
        if size[rootx] < size[rooty]:
            par[rootx] = rooty
            size[rooty] += size[rootx]
        else:
            par[rooty] = rootx
            size[rootx] += size[rooty]
        return True

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    unite(x, y)
groups = {}
for idx, p in enumerate(par):
    p = find(p)
    groups.setdefault(p, set())
    groups[p].add(idx)

cnt = 0
for k, g in groups.items():
    for gi in g:
        pi = P[gi]
        if pi in g:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
par = list(range(n))
size = [1] * n
def find(x):
    """ 根のノードの値を見つけて返す """
    if x != par[x]:
        par[x] = find(par[x])
    return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return False
    else:
        if size[rootx] < size[rooty]:
            par[rootx] = rooty
            size[rooty] += size[rootx]
        else:
            par[rooty] = rootx
            size[rootx] += size[rooty]
        return True

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    unite(x, y)
groups = {}
for idx, p in enumerate(par):
    p = find(p)
    groups.setdefault(p, set())
    groups[p].add(idx)

cnt = 0
for k, g in groups.items():
    for gi in g:
        pi = P[gi]
        if pi in g:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
l=list(map(int,input().split()))
root=[i for i in range(a)]
height=[0]*a
group=[set() for i in range(a)]
def find(a):
   f=a
   if a==root[a]:
      return a
   while a!=root[a]:
      a=root[a]
   root[f]=a
   return a
def union(a,b):
   A=find(a)
   B=find(b)
   if A==B:
      return
   if height[A]>height[B]:
      root[B]=root[A]
   else:
      root[A]=root[B]
      if height[A]==height[B]:
         height[B]+=1
for i in range(b):
   x,y=map(int,input().split())
   x-=1;y-=1
   union(x,y)
for i in range(a):
   group[root[find(i)]].add(l[i])
ans=0
for i in range(a):
   if i+1 in group[find(i)]:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
def root(i):
  if par[i] == i:
    return i
  par[i] = root(par[i])
  return par[i]

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

def same(x, y):
  return par[x] == par[y]

n,m = map(int, input().split(" "))
p = [0] + list(map(int, input().split(" ")))
a = [(list(map(int, input().split(" ")))) for i in range(m)]
par = list(range(n + 1))
count = 0
for i, j in a:
  union(i, j)
  #print(par)
#print(p)
for i in range(1, n + 1):
  if same(root(par[p[i]]), root(par[i])):
    count += 1
print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

out=0
for i in range(M):
    a,b = list(map(int,input().split()))
    Network.union(a-1,b-1)

out=[-1]*N
for i in range(N):
    if Network.same(i,p[i]-1)==False and out[i]==-1:
        out[i]=0
    else:
        out[i]=1
    # print('i,p[i]-1,out:',i,p[i]-1,out)
print(sum(out))

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
p=list(map(int,input().split()))
ab=[[] for _ in range(n+1)]
ab_dict={}
count=0
for i in range(1,n+1):
    ab_dict[p[i-1]]=i
    if p[i-1]==i:
        count+=1
for i in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
visited=[1]+[0]*(n)
su=[]
for i in range(1,n+1):
    if visited[n]==0:
        temp=set()
        temp.add(i)
        stack=deque()
        stack.append(i)
        visited[i]+=1
        while stack:
            x=stack.pop()
            for j in ab[x]:
                if visited[j]==0:
                    visited[j]+=1
                    stack.append(j)
                    temp.add(j)
        su.append(temp)

for k in su:
    for l in k:
        if ab_dict[l] in k and ab_dict[l]!=l:
            count+=1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
pa=list(range(n))
def find(u):
  if u!=pa[u]:pa[u]=find(pa[u])
  return pa[u]
for i in range(m):
  a,b=map(int,input().split())
  a=find(a-1)
  b=find(b-1)
  if a!=b:pa[a]=b
c=0
for i in range(n):
  if find(p[i]-1)==find(i):c+=1
print(c)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）"""
        tmp = []
        parents = self.parents
        while parents[x] >= 0:
            tmp.append(x)
            x = parents[x]
        for y in tmp:
            parents[y] = x
        return x

    def union(self, x, y):
        """ 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """ xとyが同じ根の子かを判定 """
        return self.find(x) == self.find(y)

    def size(self, x):
        """ xの根のparent（= 要素数）を返す """
        return -self.parents[self.find(x)]

    def members(self, x):
        """ xが属するグループの要素をリストとして返す """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """ 全ての根の要素をリストとして返す """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """ グループの数を返す """
        return len(self.roots())

    def size_list(self):
        """ 各グループの要素数のリストを返す(根の番号は返さない) """
        return [-x for x in self.parents if x < 0]

    def all_group_members(self):
        """ {根:[根の子のリスト],...}を辞書で返す """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


##############################################################################################################
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
P = list(map(int, input().split()))
U = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    U.union(a, b)
res = 0
for i, p in enumerate(P):
    if U.same(p-1,i):
        res += 1
print(res)

Submission status: Accepted

Solution code:
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    n, m = map(int, input().split())
    p = list(map(int, input().split()))

    uf = UnionFind(n)
    for _ in range(m):
        i, j = map(int, input().split())
        uf.union(i-1, j-1)
    
    ans = 0
    for i in range(n):
        if uf.same(i, p[i]-1):
            ans += 1
    
    print(ans)

main()