ARC097 D - Equals

提出

code: python

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

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

# UnionFindをどう使うか

解答

code: python

class UnionFind:

def __init__(self, n):

def _root(self, x):

return x

else:

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

if d1 <= d2:

if d1 == d2:

else:

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

UF = UnionFind(n)

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

# 入れ替え可能ならば同じ集合に属している

for _ in range(m):

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

x -= 1

y -= 1

UF.union(x, y)

ans = 0

# 例えば i=1 を考えると1が属する集合と、p1=5 が属する集合が同じであれば、5をp5の位置に持ってくることが出来る。

for i, x in enumerate(p):

if UF.find(i, x - 1):

ans += 1

print(ans)

テーマ

メモ